# Is it possible fo find a vertex-cover of size $\lceil \log |V| \rceil$ in polynomial time?

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

• The answer to your question is yes. Mar 26 at 16:37
• @PålGD How can I solve it? Mar 26 at 16:43
• Look at the next uncovered edge and choose which vertex should cover it (try both options).
– user114966
Mar 26 at 17:40
• What have you tried? Is this homework? Mar 26 at 18:00
• @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 Mar 26 at 18:55

## 1 Answer

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 )$$.