Maximal non-reducible vertex cover of a graph

Question

Let $G=(V,E)$ be a graph (i.e. an undirected simple finite graph). We say that a 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?

Answer 1

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 2

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.