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):
$R-COV(G,k)$
$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.