Vertex Cover and Independent Set

Two Complementary Ways to Describe Vertices

To cover every edge, a chosen set of vertices must meet each edge at one or both endpoints. An independent set instead avoids taking both endpoints of any edge. These conditions are complementary: every vertex not selected for a cover must be safe to select together, because no edge can have both endpoints outside the cover. This simple observation gives an exact relationship between the two decision problems and transfers computational hardness from one to the other.

All graphs in this tutorial are finite and simple. A set \(C\subseteq V(G)\) is a vertex cover if every edge of \(G\) has at least one endpoint in \(C\). A set \(I\subseteq V(G)\) is an independent set if no edge has both endpoints in \(I\). The minimum size of a vertex cover is the vertex cover number \(\tau(G)\), and the maximum size of an independent set is the independence number \(\alpha(G)\).

“At most” for a cover and “at least” for an independent set are important: these are decision versions of minimum and maximum problems. An empty set is a cover of an edgeless graph, and every subset of the vertices of an edgeless graph is independent. Isolated vertices create no edge constraint: they may be left out of a cover, and they may be included in an independent set.

The Complement Correspondence

Proof. Put \(I=V\setminus C\). Suppose first that \(C\) is a vertex cover. If \(I\) were not independent, some edge \(uv\in E\) would have both endpoints in \(I\). Neither endpoint would then belong to \(C\), contradicting that \(C\) meets every edge. Thus \(I\) is independent. Conversely, suppose \(I\) is independent and let \(C=V\setminus I\). If an edge \(uv\) had neither endpoint in \(C\), then both \(u\) and \(v\) would belong to \(I\), contradicting independence. Every edge therefore has an endpoint in \(C\), so \(C\) is a vertex cover. This argument also applies when \(V\) or \(E\) is empty. \(\square\)

Taking sizes in the correspondence gives \(|C|+|V\setminus C|=|V|\). It follows that the two extremal parameters satisfy

Indeed, if \(I\) is a largest independent set, then \(V\setminus I\) is a cover of size \(|V|-\alpha(G)\), so \(\tau(G)\le |V|-\alpha(G)\). If \(C\) is a smallest cover, then \(V\setminus C\) is independent of size \(|V|-\tau(G)\), so \(\alpha(G)\ge |V|-\tau(G)\). These inequalities give equality. No assumption that the graph is connected or has an edge is needed.

Reducing Independent Set to Vertex Cover

A polynomial-time many-one reduction converts each input of one decision problem into an input of another in polynomial time, preserving the yes-or-no answer. For an Independent Set instance \((G,k)\), let \(n=|V(G)|\). When \(0\le k\le n\), define the output instance to be \((G,n-k)\) for Vertex Cover. The graph is unchanged; only the bound is transformed.

Proof. If \(I\) is independent with \(|I|\ge k\), then \(C=V(G)\setminus I\) is a vertex cover by the complement correspondence. Its size is \(|C|=n-|I|\le n-k\). Conversely, if \(C\) is a vertex cover with \(|C|\le n-k\), then \(I=V(G)\setminus C\) is independent and has size \(|I|=n-|C|\ge k\). Both implications use the same graph and the exact complement relation, so the reduction preserves yes and no answers. \(\square\)

The transformation calculates \(n-k\) and copies the graph, so its running time is polynomial in the input length. If the source convention allows \(k>n\), that case is always a no-instance of Independent Set and can be mapped to the fixed no-instance \((K_2,0)\) of Vertex Cover: the sole edge of \(K_2\) cannot be covered by a set of size zero. Thus the reduction can be made total under that convention as well. The usual source problem Independent Set is NP-complete; using the reduction above establishes NP-hardness of Vertex Cover.

Why Vertex Cover Is in NP

A certificate for a yes-instance \((G,b)\) is a list or bit string specifying a candidate set \(C\subseteq V(G)\). A verifier checks that \(|C|\le b\), then checks every edge and accepts exactly when at least one endpoint of each edge belongs to \(C\). The size check takes polynomial time, and checking all \(m=|E(G)|\) edges takes polynomial time in a standard graph encoding. A yes-instance has such a certificate, and every accepted certificate really is a cover of the required size. Therefore Vertex Cover belongs to NP.

NP-Completeness

Proof. Membership in NP follows from the certificate verifier above. For NP-hardness, reduce from Independent Set, which is NP-complete by the earlier material on that problem. Given an instance \((G,k)\) with \(0\le k\le |V(G)|\), output \((G,|V(G)|-k)\). The transformation is polynomial-time, and the proved equivalence shows that the input is yes exactly when the output is yes. Hence Independent Set reduces to Vertex Cover, so Vertex Cover is NP-hard. More explicitly, every problem in NP reduces to Independent Set; composing that reduction with this one gives a polynomial-time reduction to Vertex Cover. Together with membership in NP, this proves NP-completeness. \(\square\)

A Direction Pitfall

The numerical bound changes from \(k\) to \(n-k\), not to \(k\). For example, if \(n=4\) and \(k=2\), the correct cover bound is \(4-2=2\). A common wrong calculation is to leave the bound at \(2\) and claim it represents the complement correspondence in general. That happens to give the same number for this particular choice, so it does not test the formula. With \(n=5\) and \(k=2\), the correct output bound is \(5-2=3\), not \(2\): an independent set of size \(2\) has a complement of size \(3\). In general the proof requires \(|V\setminus I|=n-|I|\); reversing or omitting this subtraction can reverse the decision condition.

The correspondence also does not say that a particular independent set has minimum complement among all vertex covers unless the independent set is maximum. The identity \(\tau(G)+\alpha(G)=n\) compares the optimum sizes. For a decision reduction, however, no optimization algorithm is needed: the exact complement equivalence proves that the chosen thresholds preserve the answer.