2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ This is an interesting reformulation, but can it be used to say anything about the complexity of the problem? For instance, does bounding the number of literals bound the complexity in any way? [Edited because I answered my other question about the bound on the number of literals.] Thanks. $\endgroup$ – user437459 Sep 19 '17 at 6:39
  • $\begingroup$ It shows that the decision version of the problem is in NP. $\endgroup$ – Fabio Somenzi Sep 19 '17 at 12:01
  • $\begingroup$ Fabio, thanks for your patience as this is not really my area. I'm hoping you'll elaborate a bit more. I understand the encoding of the problem as a SAT problem, and I understand SAT is NP-hard in general. But take any graph problem solvable in polynomial time, this would still have some encoding as a SAT problem, so the existence of the mapping doesn't by itself prove anything. What is the step that I'm missing? I'll accept this as an answer as soon as I can understand that missing piece. $\endgroup$ – user437459 Sep 19 '17 at 14:42
  • $\begingroup$ You are correct in noting that the existence of a SAT encoding doesn't prove NP-hardness. I only claimed that the problem is in NP. That is, given a purported solution, checking that it has size at least $k$ and that it is a minimal vertex cover is easily done in polynomial time. In fact, one doesn't even need the CNF formula for that. What really matters is the criterion to check minimality, which can be applied directly to the graph. I suspect a reduction from SAT to this problem is not too hard, but I haven't had the time to try it yet. $\endgroup$ – Fabio Somenzi Sep 19 '17 at 17:07
  • $\begingroup$ Aha, I misinterpreted your statement as saying the problems had equivalent complexity, though I see now that you made no such claim! $\endgroup$ – user437459 Sep 19 '17 at 18:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.