independent set

An independent set is the opposite of a clique. Instead of a group where everyone is connected, it is a group where NO two members are connected: a set of mutual strangers, with no edge between any pair. Picture choosing committee members who must have no conflicts of interest: any two who share an edge cannot both serve. The independent set problem asks whether you can find such a conflict-free group of at least a given size k.

Formally, an independent set in an undirected graph G is a set of vertices with no edge between any two of them. The decision problem INDEPENDENT-SET takes G and a number k and asks whether an independent set of size k exists. It is in NP: the candidate set is the certificate, and a verifier checks in polynomial time that none of its internal pairs is an edge. The three sibling problems form a tight cluster: an independent set in G is exactly a clique in the complement graph G-bar, and the complement (within the vertex set) of an independent set is a vertex cover. So a size-k independent set, a size-k clique in G-bar, and a size-(n - k) vertex cover all say the same thing.

Because of these equivalences, INDEPENDENT-SET is NP-complete: hardness flows in from CLIQUE (via complementation) or directly from 3-SAT, and membership in NP is obvious. The trio CLIQUE / INDEPENDENT-SET / VERTEX-COVER is usually taught together precisely because one quick reduction connects all three. Independent set also models real packing-without-conflict tasks, like scheduling non-overlapping events or selecting non-interfering wireless channels, which is why it shows up constantly in applications even though its general version is intractable.