1
$\begingroup$

If we know the vertex cover number for a simple graph $G$ denoted by $\tau(G)$, is it possible to find the minimum vertex cover set for $G$‌ in quasi-polynomial time? As I found, we cannot find any quasi-polynomial time solution for NP-hard problems (or at least it is a strong conjecture) such as finding the minimum vertex covering set.

$\endgroup$

1 Answer 1

1
$\begingroup$

Suppose there is an algorithm $A(G,c)$ which runs in time $T(n)$, where $n$ is the number of vertices in $G$, as long as $c$ is the vertex cover number.

Given a graph $G$, run $A(G,0),\ldots,A(G,n)$ in parallel, for $T(n)$ time each. Some of the copies will terminate within $T(n)$, outputting a set. Out of all such outputs which are vertex covers, choose the one of minimal size. This gives an algorithm for minimum vertex cover running in time $O(nT(n))$.

$\endgroup$
2
  • $\begingroup$ So, the answer is "it is not possible". As we assumed $nT(n)$ is greater than any quasi-polynomial. Right? $\endgroup$
    – OmG
    Feb 7, 2021 at 14:57
  • $\begingroup$ It is unlikely. $\endgroup$ Feb 7, 2021 at 14:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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