Given a graph or hypergraph $G$ with vertex set $V(G)$ and edge set $E(G)$, a vertex cover is a set of vertices $C\subset V(G)$ such that every edge contains at least one vertex in the set $C$. $C$ is a minimal vertex cover if it is no longer a vertex cover after removing any element $c\in C$.
The minimum vertex cover problem, which asks for the smallest cardinality of such a set, is NP-hard. What about the complexity of finding the largest minimal vertex cover? And/or the decision problem of whether there is a minimal vertex cover of cardinality at least $k$?
As a very small example, consider a path on 5 vertices.
$v_1$ —— $v_2$ ——- $v_3$ ——- $v_4$ —— $v_5$
The maximum size of a minimal vertex cover in this graph is 3: the sets $\{v_1,v_3,v_5\}$ and $\{v_2,v_3,v_5\}$ are two examples that achieve this. Notice by the second example that these are not necessarily independent sets.
I'm interested in how to find maximum minimal vertex covers, but equally interested in determining or bounding the value of the maximum cardinality, without necessarily producing the sets.
The answer to this question mentions the idea of a maximum minimal vertex cover, but doesn't say anything about computing such a thing. I was unable to find another discussion of the subject.
Best Answer
One can encode this problem as a maximum-cost propositional SAT problem.
Let there be a propositional variable $x_v$ for each vertex $v$ in the graph. There are two types of constraints:
Covering constraints: for each edge $(u,v)$, one endpoint must be included. That is, $x_u \vee x_v$ must hold.
Minimality constraints: suppose vertex $v$ has neighbors $u_1,\ldots, u_k$; $v$ can be removed if and only if all its neighbors are included in the cover. The constraint for $v$ is therefore $\neg x_v \vee \neg x_{u_1} \vee \cdots \vee \neg x_{u_k}$. (If vertex $v$ is isolated, its minimality constraint boils down to $\neg x_v$.)
If the graph has $n$ nodes and $e$ edges, the number of literals in the CNF formula is at most $n + 4e$. It is "at most," because some minimality constraints are subsumed by others. In the example above, the minimality constraints for $v_2$ and $v_4$ are subsumed by the constraints for $v_1$ and $v_5$, respectively. Once subsumed constraints are removed, the CNF formula cannot be further simplified.
One then looks for a satisfying assignment that has the greatest number of asserted variables.
We now show that the decision version of the problem (does this graph have a minimal vertex cover of size at least $k$?) is NP-complete. The proof is also going to work for size exactly equal to $k$.
The problem is in NP because a solution can be verified in polynomial time by checking that it has the required size and satisfies all constraints. As noted in the comments, this does not require translation to SAT.
We show that the problem is NP-hard by reducing CNF SAT to it. The strategy is adapted from M. D. Plummer, "Well-covered graphs: a survey", Quaestiones Mathematicae, 16(3):253–287, 1993.
Suppose we are given a propositional CNF formula $F$ that contains at least one clause, no empty clause, and no repeated clauses. Furthermore, no clause contains both a variable and its negation, or repeated literals. If any of these conditions are violated, either satisfiability is trivially decided (e.g., $F$ contains the empty clause) or $F$ can be easily simplified.
Let $F$ consists of $n$ clauses over $k$ variables. We create a graph $G$ as follows. There are $2k+n$ vertices: one vertex for each literal and one for each clause. Each literal is connected to its negation. Each clause is connected to all other clauses. (The clause vertices form a clique of size $n$.) Finally, every clause is connected to all its literals. This construction can be completed in polynomial time.
It is readily seen that an independent set of $G$ may contain at most one clause vertex and at most $k$ literal vertices. We can take this one step further: if $F$ is satisfiable, there are maximal independent sets of sizes $k$ and $k+1$, whereas if $F$ is unsatisfiable, all maximal independent sets have size $k+1$.
In fact, an assignment to the $k$ variables of $F$ identifies an independent subset of the literals of size $k$. If the assignment satisfies all clauses, no clause vertex can be added to this independent set, which is therefore maximal; otherwise, one of the unsatisfied clauses can be added to the set.
Regardless of whether $F$ is satisfiable, we can build a maximal independent set of size $k+1$ as follows: we pick one clause and an independent set of $k$ literals that are not in the clause. (That is, for every literal in the clause, we pick its negation, and for every variable not in the clause, we pick one of its literals.)
In sum, $F$ is satisfiable if and only if $G$ has maximal independent sets of size $k$. Said otherwise, $F$ is satisfiable if and only if $G$ has minimal vertex covers of size at least $k+n$.