If we have a graph $G=(V,E)$, can we find a vertex cover with size $\lceil \log |V| \rceil$ in polynomial time?

  • $\begingroup$ The answer to your question is yes. $\endgroup$
    – Pål GD
    Mar 26 at 16:37
  • $\begingroup$ @PålGD How can I solve it? $\endgroup$
    – thatUser
    Mar 26 at 16:43
  • $\begingroup$ Look at the next uncovered edge and choose which vertex should cover it (try both options). $\endgroup$
    – user114966
    Mar 26 at 17:40
  • $\begingroup$ What have you tried? Is this homework? $\endgroup$
    – Pål GD
    Mar 26 at 18:00
  • $\begingroup$ @PålGD no, this is a question I had on my first term exam. I tried to use the FPT-Approach by having the paramater = ⌈log |V|⌉ which is a constant, but this was not sufficient $\endgroup$
    – thatUser
    Mar 26 at 18:55

Let the input graph be $G=(V,E)$ and let $k$ be the (maximum) size of the vertex cover of $G$ we are searching for. Proceed as follows:

  • If $E=\emptyset$ return the trivial empty solution.
  • Otherwise, if $k>0$:
    • Pick an arbitrary edge $(u,v) \in E$.
    • Recursively search for a vertex cover $S$ of size (at most) $k-1$ on the graph $G - u$. If $S$ exists return $S \cup \{u \}$.
    • Recursively search for a vertex cover $S$ of size (at most) $k-1$ on the graph $G-v$. If $S$ exists return $S \cup \{v \}$.
  • Return "no solution exists".

The time complexity of the above algorithm can be described by the following recurrence relation, where $n$ is the number of vertices of the input graph for your problem.

$$ T(k) \le 2T(k-1) + O(\mbox{poly}\, n) \quad \mbox{and} \quad T(0)=O(1). $$

Therefore $T(k) = O( 2^k \cdot \mbox{poly}\, n )$. In your case $k=\lceil \log n \rceil$, therefore the overall time needed is $O( \mbox{poly}\, n )$.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.