# Number of bounded minimum vertex covers

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

• 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? – Gamow Nov 28 '16 at 9:09
• i.e C= number of minimum vertex covers of size at most $k$. What is the value of C in f(k). – GOLD Nov 28 '16 at 9:15
• crossposted from stackoverflow after less than 3 hours without mentioning that on either site ​ ​ – user6973 Nov 30 '16 at 5:29

## 1 Answer

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