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.
1 Answer
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))$.
-
$\begingroup$ So, the answer is "it is not possible". As we assumed $nT(n)$ is greater than any quasi-polynomial. Right? $\endgroup$– OmGFeb 7, 2021 at 14:57
-