Introduction Given a graph $G = (V, E)$, we call a set $T \subseteq V$ a cover if any edge $e \in E$ has one extremity in T.

Decision Problem: Given $G = (V, E)$ with n nodes and a $k \le n$, return Yes if there exists a set T which is a cover in G, with $|T| \le k$, No otherwise.

Ok, so far so good. I'm given the following algorithm(it returns Yes/No & the set T):


$if(E = \emptyset$ then return ("Yes", $\emptyset$)

$if(|E| \gt k * (|V| - 1)$ then return ("No")

Let ${u, v} \in E$

$if( R-COV(G - u, k - 1) == ("Yes", T) )$ then return("Yes", $T \cup\{u\}$)

else $if( R-COV(G - v, k - 1) == ("Yes", T)$ then return ("Yes", $T \cup \{v\}$)

else return ("No")

I shall prove that this algorithm does exactly what's asked to do (so it is correct) and find out it's $T(n, k)$ (execution time).

What I know by now

Guessing right, this decision problem is NP-complete.

To prove it is correct, I thought of analyzing every condition in this algorithm and proving that it returns "Yes" only for T-covers.. Visually it looks right, but I don't know how to write it down mathematically..

For the execution time, should I use the Master Theorem? Is it apropriate? Also I think that when k is constant, the algorithm is, obviously, running in polynomial time. But how should I write this down mathematically?

Thanks for your time.

  • $\begingroup$ What is $R$ in your algorithm? Also you don't want to say an algorithm is NP-complete, it's the decision problem which is NP-complete. $\endgroup$ – Ben Nov 5 '15 at 22:12
  • 2
    $\begingroup$ The proof of correctness of the algorithm is given here: math.stackexchange.com/questions/1514974/… $\endgroup$ – user137481 Nov 6 '15 at 2:22
  • $\begingroup$ @user137481, thank you very much $\endgroup$ – nightwing96 Nov 7 '15 at 10:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.