<p>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.</p>

<p>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. </p>

<p>Further information can be found in  </p>

<p>Henning Fernau:
On Parameterized Enumeration. COCOON 2002: 564-573 <a href="http://dx.doi.org/10.1007/3-540-45655-4_60" rel="nofollow noreferrer">dx.doi.org/10.1007/3-540-45655-4_60</a></p>

<p>and</p>

<p>Peter Damaschke:
Parameterized enumeration, transversals, and imperfect phylogeny reconstruction. Theor. Comput. Sci. 351(3): 337-350 (2006)
<a href="http://dx.doi.org/10.1016/j.tcs.2005.10.004" rel="nofollow noreferrer">http://dx.doi.org/10.1016/j.tcs.2005.10.004</a></p>

CC BY-SA 3.0
2016-11-28T09:34:18.503Z
2016-11-28T09:34:18.503Z
Christian Komusiewicz
<p><strong>Minimum Vertex Cover problem</strong></p>

<p>Input: $G=(V,E)$ and Parameter $k$</p>

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

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

<p>C=number of minimum vertex covers of size at most $k$</p>

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

CC BY-SA 3.0
2016-11-28T09:09:54.273Z
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
CC BY-SA 3.0
2016-11-28T09:15:37.097Z
i.e C= number of minimum vertex covers of size at most $k$. What is the value of C in f(k).
GOLD
<cc.complexity-theory><graph-theory><graph-algorithms>
Number of bounded minimum vertex covers
GOLD
# Number of bounded minimum vertex covers

(Asked by: username_0 on 2016-11-28)

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

**Tags:** cc.complexity-theory, graph-theory, graph-algorithms

> **Comments:**
> **username_1**: 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?  
> **username_0**: i.e C= number of minimum vertex covers of size at most $k$. What is the value of C in f(k).  

---

## 1 answers

### Answer by username_2 on 2016-11-28. Score: 3

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](http://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>


---

