NP-Complete Problems and Reductions: A Detailed Look

Posted on Feb 19, 2025 in Computers

NP-Completeness: Key Concepts

NP (Non-deterministic Polynomial time): Problems where a proposed solution (certificate) can be verified in polynomial time. A ‘guesser’ proposes a solution, and a ‘verifier’ checks it. Both guessing and verifying happen in polynomial time.

Every problem in NP can be reduced to SAT (Satisfiability) – Cook-Levin Theorem.

Problem Definitions

Independent Set (IS)

Given a graph G = (V, E) and an integer K, is there a set I (subset of V) with |I| ≥ K such that for any u, v in I, the edge [u, v] does not belong to E? This is a maximization problem.

Vertex Cover (VC)

Given a graph G and a number K, does G have a vertex cover of size at most K? (A vertex cover is a set of vertices that includes at least one endpoint of every edge in the graph.) This is a minimization problem.

Set Cover (SC)

Given a set U of n elements and sets S1, S2, … (subsets of U), is there a collection of at most k subsets such that their union is U?

Clique

A clique in a graph is a fully connected set of nodes (all nodes are connected to each other). Is there a clique of size K or larger in the graph?

Dominating Set (DS)

A set of nodes D is a dominating set if each node either is in D or is adjacent to a node in D.

Hamiltonian Path (HP)

Given a graph, is there a path that visits each node exactly once?

Graph Coloring

Given an undirected graph, a valid vertex coloring is an assignment of a color to each vertex such that no two adjacent vertices share the same color.

Subset Sum

Is there a subset of numbers that sum to a target value z?

Traveling Salesperson Problem (TSP)

Given a list of cities and the distances between each pair of cities, what is the shortest possible route that visits each city exactly once and returns to the origin city?

3D Matching

Given three sets and a set of possible matches, can we pick one element from each set and match them all up without violating any conditions (analogous to a marriage problem with constraints)?

Bipartite Matching

Given a bipartite graph, find the largest set of edges such that no two edges share a common vertex.

NP Examples

Clique

Verification: Pick K nodes. Check if each pair of nodes in the selected set has an edge between them. (K steps to guess, K² steps to check; K² + K is polynomial).

3D Matching

Verification: Pick one element from each set (nC1) * 3. Check if it’s in the list (maximum list size = n³).

Reductions

SAT to 3SAT

3SAT to IS

IS to VC

Idea: C is a vertex cover of G = (V, E) if and only if V \ C is an independent set. This is because any two nodes not in a vertex cover cannot have an edge between them; otherwise, that edge would not be covered.

Reduction: Let S be an independent set. Consider an arbitrary edge e = (u, v). Since S is independent, it cannot be the case that both u and v are in S. Thus, at least one of u or v (or both) must be in V \ S. Therefore, V \ S must be a vertex cover.

VC to IS

Suppose V \ S is a vertex cover. Consider nodes u, v in S. If they were joined by an edge e, then neither endpoint of e would lie in V \ S, a contradiction. Thus, S must be an independent set.

IS to VC (Combined)

Given an instance (G = (V, E), K) of the independent set problem, we produce the instance (G = (V, E), |V| – K) of the vertex cover problem. There is an independent set with K nodes or more if and only if there is a vertex cover of size |V| – K or less. (Max IS ↔ Min VC).

IS to Clique

We transform the instance (G, K) of the independent set problem to the equivalent instance (G’, K), where G’ is the complement of G (the graph with the same nodes as G, but with precisely all edges that are *missing* from G).

VC to DS

To reduce an input (G, K) of VC to DS, we add to G, for each edge [a, b] in E, a new node ‘ab’ and two new edges [a, ab] and [b, ab]. Any vertex cover of G is a dominating set of the new graph. Any dominating set of the new graph can be converted into a vertex cover of G by replacing any new vertex (‘ab’) with one of its adjacent vertices (either ‘a’ or ‘b’).

VC to Set Cover (SC)

Construction: Given an instance of VC, (G = (V, E), K), we convert it to an instance of SC. Let U correspond to E (the set of edges). For each vertex i in V, we create a subset S_i (subset of U) consisting of all edges adjacent to i.

Claim: U can be covered with at most k subsets if and only if G has a vertex cover of size at most k.

Proof: If a collection of subsets (S_i1, S_i2, …, S_il), where l ≤ k, covers U, then the vertices (i1, i2, …, il) must be a vertex cover for G, and this vertex cover has size ≤ k. Conversely, if (i1, i2, …, il) is a vertex cover in G, then the sets (S_i1, S_i2, …, S_il) must cover U.