0
$\begingroup$

Minimum Vertex Cover problem

Input: $G=(V,E)$ and Parameter $k$

Output: Decide whether there exists minimum vertex cover of size at most $k$.

Question:- Can we bound the number of minimum vertex covers of size at most $k$ on general graphs?

C=number of minimum vertex covers of size at most $k$

Is C bounded by $f(k)$? If not can you provide example? If yes what is $f(k)$

Improve this question
$\endgroup$
3
  • $\begingroup$ Do you really mean the number of minimum vertex covers of size at most k, or do you mean the number of vertex covers of size at most k? $\endgroup$ – Gamow Nov 28 '16 at 9:09
  • $\begingroup$ i.e C= number of minimum vertex covers of size at most $k$. What is the value of C in f(k). $\endgroup$ – GOLD Nov 28 '16 at 9:15
  • $\begingroup$ crossposted from stackoverflow after less than 3 hours without mentioning that on either site ​ ​ $\endgroup$ – user6973 Nov 30 '16 at 5:29
3
$\begingroup$

The number of inclusion-minimal vertex covers of size at most $k$ is at most $2^k$: They can be enumerated by a search tree algorithm that initially has a budget of $k$, then branches as long as the graph contains an edge $\{u,v\}$ into the two cases to add either $u$ or $v$ to the vertex cover. Each branch can be solved recursively and the parameter $k$ is reduced by one in each case.

The number of minimal vertex covers of size at most $k$ obviously bounds the number of minimum vertex covers of size at most $k$ as well.

Further information can be found in

Henning Fernau: On Parameterized Enumeration. COCOON 2002: 564-573 dx.doi.org/10.1007/3-540-45655-4_60

and

Peter Damaschke: Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theor. Comput. Sci. 351(3): 337-350 (2006) http://dx.doi.org/10.1016/j.tcs.2005.10.004

Improve this answer
$\endgroup$

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.