NP Verification Runtimes

Question 1

Time to verify IS

Answer 1

Given an array of vertices S, we can verify that for all (x,y) in E, x or y are in S. This takes O(n+m) time.

We can verify that |S| <= b in O(n) time.

Overall, this takes O(n+m)