<p>What you call a non-reducible vertex cover is commonly known as a <em>minimal</em> vertex cover. So, what you are looking for is a minimal vertex cover of maximum cardinality, i.e a maximum minimal vertex cover.</p>

<p>I'm not aware of any literature on this problem per se, however the equivalent <em>Independent Dominating Set</em> problem is quite well studied. An <em>independent dominating set</em> in a graph $G$ is an independent set $I$ such that every vertex not in $I$ has a neighbor in $I$. In the <em>Independent Dominating Set</em> problem input is a graph $G$ and the task is to find a smallest possible independent dominating set. This problem is known to be NP-complete. </p>

<p>The two problems are equivalent because a set $S$ is a minimal vertex cover if and only if $V(G) \setminus S$ is an independent dominating set. </p>

CC BY-SA 3.0
2017-05-08T14:51:23.980Z
2017-05-08T14:51:23.980Z
daniello
<p>Since the complement of a vertex cover is an independent set, 
the problem of finding a minimal vertex cover of maximum cardinality 
is equivalent to 
the problem of finding a maximal indpendent set of minimum cardinality.</p>

<ul>
<li><p>The problem of finding a maximal indpendent set of minimum cardinality has been studied extensively. The right search term is "well-covered graphs".</p></li>
<li><p>In particular, the underlying decision problem is NP-complete. This follows (for instance) from the reduction in V. Chvátal and P.J. Slater, 
"A note on well-covered graphs" in Annals of Discrete Math 55 (1993), 179–181. </p></li>
</ul>

CC BY-SA 3.0
2017-05-08T14:58:58.203Z
2017-05-08T14:58:58.203Z
Gamow
<p>Let $G=(V,E)$ be a graph (i.e. an undirected simple finite graph). 
We say that a <a href="https://en.wikipedia.org/wiki/Vertex_cover" rel="nofollow noreferrer">vertex cover</a> $V'$ of $G$ is <em>non-reducible</em> if any $V''$ with $V''\subsetneq V'$ is not a vertex cover of $G$. We say that a non-reducible vertex cover $V'$ of $G$ is <em>maximal</em> if for all non-reducible vertex cover $V''$ of $G$ we have $|V''|\le |V'|$. Note that the minimum vertex cover is non-reducible, but of course not necessarily maximal.  </p>

<p>What is know about the (time)-complexity of finding a maximal non-reducible vertex cover? </p>

<p>Is there anything known for hypergraphs with multiple edges? </p>

<graph-theory><graph-algorithms><time-complexity>
Maximal non-reducible vertex cover of a graph
Tom
# Maximal non-reducible vertex cover of a graph

(Asked by: username_0 on 2017-05-08)

Let $G=(V,E)$ be a graph (i.e. an undirected simple finite graph).
We say that a [vertex cover](https://en.wikipedia.org/wiki/Vertex_cover) $V'$ of $G$ is *non-reducible* if any $V''$ with $V''\subsetneq V'$ is not a vertex cover of $G$. We say that a non-reducible vertex cover $V'$ of $G$ is *maximal* if for all non-reducible vertex cover $V''$ of $G$ we have $|V''|\le |V'|$. Note that the minimum vertex cover is non-reducible, but of course not necessarily maximal.

What is know about the (time)-complexity of finding a maximal non-reducible vertex cover?

Is there anything known for hypergraphs with multiple edges?

**Tags:** graph-theory, graph-algorithms, time-complexity

---

## 2 answers

### Answer by username_1 on 2017-05-08. Score: 3

What you call a non-reducible vertex cover is commonly known as a *minimal* vertex cover. So, what you are looking for is a minimal vertex cover of maximum cardinality, i.e a maximum minimal vertex cover.

I'm not aware of any literature on this problem per se, however the equivalent *Independent Dominating Set* problem is quite well studied. An *independent dominating set* in a graph $G$ is an independent set $I$ such that every vertex not in $I$ has a neighbor in $I$. In the *Independent Dominating Set* problem input is a graph $G$ and the task is to find a smallest possible independent dominating set. This problem is known to be NP-complete.

The two problems are equivalent because a set $S$ is a minimal vertex cover if and only if $V(G) \setminus S$ is an independent dominating set.


---

### Answer by username_2 on 2017-05-08. Score: 3

Since the complement of a vertex cover is an independent set,
the problem of finding a minimal vertex cover of maximum cardinality
is equivalent to
the problem of finding a maximal indpendent set of minimum cardinality.

* The problem of finding a maximal indpendent set of minimum cardinality has been studied extensively. The right search term is "well-covered graphs".
* In particular, the underlying decision problem is NP-complete. This follows (for instance) from the reduction in V. Chvátal and P.J. Slater,
  "A note on well-covered graphs" in Annals of Discrete Math 55 (1993), 179–181.


---

