<p>The algorithm fails in the case, when there are no edges left to cover, because then it does not have a structure to branch on. Consider for example the case where the graph is edgeless, then we have <span class="math-container">$\sum_{i=0}^{k} \binom{n}{i}$</span> vertex covers of size at most <span class="math-container">$k$</span>, with all of them except the empty set being nonminimal. The algorithm fails since it never finds an edge to branch on.</p>
<p>For an example where every vertex is incident with at least one edge, one may consider a star graph with center vertex <span class="math-container">$u$</span> and <span class="math-container">$n$</span> leaves. For <span class="math-container">$n&gt;k$</span>, this graph has <span class="math-container">$\sum_{i=0}^{k-1} \binom{n}{i}$</span> vertex covers of size at most <span class="math-container">$k$</span>, all vertex covers contain the center <span class="math-container">$u$</span> and again all vertex covers except one of them are nonminimal. Here the branching algorithm also fails, since after inclusion of <span class="math-container">$u$</span>, there are no edges left to branch on: if you consider such an edge <span class="math-container">$\{u,v\}$</span> then it does not hold that every desired vertex cover must contain some further vertex from this edge since the edge is already covered by <span class="math-container">$u$</span>.</p>
<p>Some discussion on this topic can also be found in</p>
<p>Henning Fernau: On Parameterized Enumeration. COCOON 2002: 564-573</p>

CC BY-SA 4.0
2024-02-27T14:00:01.170Z
2024-02-27T14:00:01.170Z
Christian Komusiewicz
<p>I am looking into the problem to generate all possible vertex covers (including both minimal vertex covers and non-minimal vertex covers) of size at most <span class="math-container">$k$</span>? Is there any algorithm that can achieve this?</p>
<p>I tried the exhaustive approach where for every edge <span class="math-container">$\{u,v\}$</span>, either <span class="math-container">$u$</span> is in the vertex cover, <span class="math-container">$v$</span> is in the vertex cover or both are in the vertex cover, and we repeat this <span class="math-container">$k$</span> times. But will this algorithm generate non-minimal vertex cover solutions too?</p>
<p>I am confused because there are <span class="math-container">$\binom{n}{k}$</span> subsets of size <span class="math-container">$k$</span>, and hence <span class="math-container">$\binom{n}{k}$</span> solutions are possible. So, I am confused on how this algorithm will work in <span class="math-container">$3^k$</span> time.</p>

<parameterized-complexity><vertex-cover>
Enumerating all Vertex Covers of Size at most $k$
Sugyani
# Enumerating all Vertex Covers of Size at most $k$

(Asked by: username_0 on 2024-02-25)

I am looking into the problem to generate all possible vertex covers (including both minimal vertex covers and non-minimal vertex covers) of size at most $k$? Is there any algorithm that can achieve this?

I tried the exhaustive approach where for every edge $\{u,v\}$, either $u$ is in the vertex cover, $v$ is in the vertex cover or both are in the vertex cover, and we repeat this $k$ times. But will this algorithm generate non-minimal vertex cover solutions too?

I am confused because there are $\binom{n}{k}$ subsets of size $k$, and hence $\binom{n}{k}$ solutions are possible. So, I am confused on how this algorithm will work in $3^k$ time.

**Tags:** parameterized-complexity, vertex-cover


---

## 1 answers

### Answer by username_1 on 2024-02-27. Score: 3 | Accepted answer

The algorithm fails in the case, when there are no edges left to cover, because then it does not have a structure to branch on. Consider for example the case where the graph is edgeless, then we have $\sum\_{i=0}^{k} \binom{n}{i}$ vertex covers of size at most $k$, with all of them except the empty set being nonminimal. The algorithm fails since it never finds an edge to branch on.

For an example where every vertex is incident with at least one edge, one may consider a star graph with center vertex $u$ and $n$ leaves. For $n>k$, this graph has $\sum\_{i=0}^{k-1} \binom{n}{i}$ vertex covers of size at most $k$, all vertex covers contain the center $u$ and again all vertex covers except one of them are nonminimal. Here the branching algorithm also fails, since after inclusion of $u$, there are no edges left to branch on: if you consider such an edge $\{u,v\}$ then it does not hold that every desired vertex cover must contain some further vertex from this edge since the edge is already covered by $u$.

Some discussion on this topic can also be found in

Henning Fernau: On Parameterized Enumeration. COCOON 2002: 564-573


---

