Independent Set Through Graph Complements

Independent Sets and Complement Graphs

A graph complement changes which pairs of distinct vertices are adjacent, but it does not change the vertices themselves. That makes it a natural way to translate between two questions: whether a vertex set contains no adjacent pair, and whether every pair in a vertex set is adjacent. The translation preserves the size of the set exactly, so it also preserves the threshold in the corresponding decision problems.

A set \(S\subseteq V(G)\) is independent if no two distinct vertices of \(S\) are adjacent in \(G\). A set \(S\subseteq V(G)\) is a clique if every two distinct vertices of \(S\) are adjacent in \(G\). These definitions include the empty set and every one-vertex set: the conditions on pairs are vacuously satisfied when there are fewer than two vertices.

Proof. Fix any \(S\subseteq V(G)\). Suppose first that \(S\) is independent in \(G\). For any two distinct vertices \(u,v\in S\), independence says \(uv\notin E(G)\). By the definition of the complement, this means \(uv\in E(\overline{G})\). Since this holds for every distinct pair in \(S\), the set \(S\) is a clique in \(\overline{G}\). Conversely, suppose \(S\) is a clique in \(\overline{G}\). For any two distinct vertices \(u,v\in S\), we have \(uv\in E(\overline{G})\), so the definition of the complement gives \(uv\notin E(G)\). Therefore \(S\) is independent in \(G\). If \(S\) has zero or one vertex, both pair conditions hold vacuously, so the two implications also cover those cases. \(\square\)

The set \(S\) in the theorem is literally the same subset of vertices on both sides: only the graph in which we test it changes. Consequently, its size is unchanged. In particular, for every nonnegative integer \(k\), \(G\) has an independent set of size at least \(k\) exactly when \(\overline{G}\) has a clique of size at least \(k\). This includes \(k=0\), since the empty set qualifies on both sides. If \(k>|V(G)|\), neither graph can have a set of that size.

Computing and Checking the Correspondence

For a graph with \(n\) vertices, there are \(\binom{n}{2}=n(n-1)/2\) possible edges. To construct \(\overline{G}\), keep the same vertex set and inspect each possible pair once, adding the pair precisely when it is absent from \(E(G)\). This takes polynomial time: with an adjacency matrix, the entries can be complemented off the diagonal; with an explicit vertex-and-edge-list encoding, one can inspect at most \(n(n-1)/2\) pairs and test whether each appears in the edge list. The output has at most \(\binom{n}{2}\) edges, so its size is polynomial in the size of the explicit input. The parameter \(k\) is copied unchanged.

The correspondence can also be seen by counting edges. If \(G\) has \(n\) vertices and \(m\) edges, then the possible pairs split into the edges of \(G\) and the edges of \(\overline{G}\), with no overlap. Therefore \(|E(\overline{G})|=\binom{n}{2}-m\). This count is a useful check on a complement construction; it does not itself decide whether a particular vertex set is independent or a clique.

From Clique to Independent Set

A decision problem asks whether an input has a specified property. Clique has instances \((G,k)\) and answers yes exactly when \(G\) has a clique of size at least \(k\). Independent Set has instances \((H,k)\) and answers yes exactly when \(H\) has an independent set of size at least \(k\). Here graphs are finite and simple, and \(k\) is a nonnegative integer. A polynomial-time many-one reduction from a problem \(A\) to a problem \(B\) is a polynomial-time computable map from instances of \(A\) to instances of \(B\) that preserves the yes-or-no answer.

Proof. First, Independent Set belongs to NP. A certificate for a yes-instance \((H,k)\) is a list of vertices forming a set \(S\). A verifier checks that every listed vertex belongs to \(V(H)\), that there are no repetitions, that \(|S|\ge k\), and that none of the pairs of distinct vertices in \(S\) is an edge of \(H\). These checks take polynomial time in an explicit graph encoding. If \(k>|V(H)|\), the verifier rejects, since no such set can exist. If \(k=0\), it accepts the empty set, which satisfies the condition. Thus a yes-instance has a polynomial-size certificate verified in polynomial time.

For NP-hardness, use the map \(f(G,k)=(\overline{G},k)\), with source problem Clique and target problem Independent Set. The complement construction is polynomial-time, as shown above, and copying \(k\) takes polynomial time. For every input \((G,k)\), the set correspondence gives

Therefore \(f\) is a polynomial-time many-one reduction from Clique to Independent Set. Clique is NP-complete by the earlier result on reducing 3-SAT to Clique, so in particular Clique is NP-hard. Since every instance of Clique is mapped in polynomial time to an equivalent instance of Independent Set, every problem in NP that reduces to Clique also reduces to Independent Set by composing the reductions. Hence Independent Set is NP-hard. Together with its membership in NP, this proves that Independent Set is NP-complete. \(\square\)

The direction is essential. To prove that a target problem is NP-hard using a problem already known to be NP-hard, the reduction must start with instances of the known hard problem and produce instances of the target. Here the input is a Clique instance \((G,k)\), and the output is an Independent Set instance \((\overline{G},k)\). The equivalence above verifies the answer in precisely that direction.

Common Reduction Pitfall

A frequent error is to reverse the reduction arrow. The complement identity also says that an Independent Set instance \((G,k)\) has the same answer as the Clique instance \((\overline{G},k)\). That describes a reduction from Independent Set to Clique. By itself, a reduction from the target problem to a known NP-hard problem does not establish that the target is NP-hard: it does not show how to solve every known hard instance using the target problem.

There is also a concrete mistake in treating complementation as if it preserved cliques. Let \(G=K_3\), with \(V=\{1,2,3\}\), \(E=\{12,13,23\}\), and \(k=3\). The input is a yes-instance of Clique. Its complement has the same three vertices and no edges, so it is not a yes-instance of Clique at threshold \(3\). Thus the claim “\(G\) has a clique of size at least \(k\) if and only if \(\overline{G}\) has a clique of size at least \(k\)” is false for this explicit input. The correct output question is Independent Set: \(\overline{G}\) has the independent set \(\{1,2,3\}\) of size \(3\). The valid equivalence is Clique in \(G\) if and only if Independent Set in \(\overline{G}\).

The complement construction is useful because it transfers a decision problem without changing the threshold or the chosen vertex set, and its computational cost is polynomial. Its simplicity does not remove the need to check the reduction's source, target, and yes/no equivalence separately.