Difficulty: Advanced | Prerequisites: P, NP, NP-hardness; efficient verifiers; polynomial-time mapping reductions; 3SAT and CLIQUE NP-completeness from lecture; vertex cover reduction from lecture.
This topic puts together everything from the earlier notes. NP-completeness proofs have two halves: showing the problem is in NP (build a verifier) and showing it is NP-hard (build a reduction from a known NP-hard problem). The homework covers three problems: Dominating Set (NP-complete, via reduction from 3SAT), Subgraph Isomorphism (NP-complete, via reduction from CLIQUE), and BIG-IS (a variant of Independent Set that turns out to be in P). The last one is a reminder that not every problem that looks hard actually is.
Dominating Set is NP-complete: the verifier checks a proposed dominating set in poly time, and the reduction from 3SAT uses variable gadgets (four vertices per variable) plus clause vertices. Subgraph Isomorphism is NP-complete: the verifier checks a proposed subgraph and mapping, and the reduction from CLIQUE maps (G, k) to (G, K_k). BIG-IS (independent set of size |V| - 1) is in P because there are only |V| subsets of that size to check.
Dominating set
A subset D of vertices in a graph G = (V, E) such that every vertex in V is either in D or adjacent to a vertex in D. Think of it as: placing guards so that every room in a building is either guarded or next to a guarded room.
Vertex cover
A subset C of vertices such that every edge in E has at least one endpoint in C. Related but different: a dominating set of {a} in a triangle does not cover the edge (b, c), but a vertex cover {b, c} does.
Variable gadget (in the 3SAT to Dominating Set reduction)
Four vertices per variable x_i: T_i (true), F_i (false), alpha_i, and beta_i. Edges connect T_i and F_i to each other and to both alpha_i and beta_i. Forces exactly one of T_i or F_i into any dominating set of size n.
Subgraph
A graph G' = (V', E') where V' is a subset of V and E' is a subset of E.
Graph isomorphism
A bijection f: V to W between two graphs such that (u, v) is an edge iff (f(u), f(v)) is an edge. Preserves structure exactly.
Subgraph Isomorphism (the language)
{(G, H) : G has a subgraph isomorphic to H}. NP-complete.
Independent set
A subset I of vertices where no two vertices in I share an edge.
BIG-IS
{G : G has an independent set of size at least |V| - 1}. Equivalent to asking whether removing some single vertex leaves an edge-free graph. In P.
Complete graph K_k
The graph on k vertices where every pair is connected by an edge. A clique of size k in G is a subgraph isomorphic to K_k.
Certificate: a subset V' of V (at most |V| vertices, so polynomial size).
Verifier: check |V'| = k, then for each v in V', remove v and all its neighbours from V. If V is empty afterwards, accept; otherwise reject.
Correctness: V is empty iff every vertex was either in V' or adjacent to something in V'.
Runtime: iterating through V' takes at most |V| steps; neighbour removal is polynomial.
Given a 3CNF formula phi with n variables and m clauses, construct graph G and set k = n.
Variable gadget for each x_i: four vertices T_i, F_i, alpha_i, beta_i with edges (T_i, F_i), (alpha_i, T_i), (alpha_i, F_i), (beta_i, T_i), (beta_i, F_i).
Clause vertex for each clause C_j: one vertex with edges to T_i if x_i appears in C_j, and to F_i if the negation of x_i appears in C_j.
Forward direction (phi is satisfiable implies dominating set exists): pick T_i if x_i is true, F_i if false. This dominates all four vertices in each gadget (alpha_i and beta_i are adjacent to both T_i and F_i). Each clause vertex is adjacent to at least one selected vertex because the clause has a true literal.
Reverse direction (dominating set of size n implies phi is satisfiable): alpha_i and beta_i have no clause neighbours, so each gadget must contribute at least one vertex to the dominating set. With budget n, exactly one of T_i or F_i is chosen per gadget. Since alpha_i and beta_i are not adjacent to each other, the chosen vertex must be T_i or F_i (not alpha_i or beta_i). Each clause vertex must have a neighbour in the set, which means at least one literal per clause is true.
Runtime: O(1) vertices and edges per variable and clause, so the construction is polynomial.
Certificate: a proposed subgraph G' of G and a bijection f from V(G') to V(H).
Verifier: check G' is a valid subgraph of G, f is a valid relabelling, and f(G') has the same edge set as H.
Runtime: checking edges takes O(|V|^2) with adjacency matrices.
Given (G, k) where G = (V, E), map to (G, K_k) if k <= |V|, or to (empty graph, single-vertex graph) if k > |V|.
Correctness: G has a clique of size k iff G has a subgraph isomorphic to the complete graph K_k. The k > |V| case maps a "no" CLIQUE instance to a "no" Subgraph Isomorphism instance (an empty graph has no subgraph with a vertex).
Runtime: generating K_k is O(k^2), and k <= |V| in the non-trivial case, so this is polynomial.
Note: unconditionally generating K_k without the k <= |V| guard would be a mistake, because k could be exponentially large (encoded in binary).
BIG-IS asks: does G have an independent set of size |V| - 1?
There are exactly |V| subsets of size |V| - 1 (each formed by removing one vertex).
Algorithm: for each vertex w, remove w and check whether the remaining graph has any edges. If it does not, accept.
Runtime: |V| iterations, each checking O(|V|^2) edges. Total: O(|V|^3), polynomial.
Intuition: the problem looks like Independent Set (which is NP-complete), but the specific budget of |V| - 1 collapses the search space to a polynomial number of candidates.
Students often confuse dominating sets with vertex covers. A dominating set requires every vertex to be in D or adjacent to D. A vertex cover requires every edge to have at least one endpoint in C. They overlap but are not the same.
In the 3SAT to Dominating Set reduction, students sometimes forget why alpha_i and beta_i are needed. Without them, the dominating set could include clause vertices or skip variable gadgets, breaking the correspondence between the dominating set and a satisfying assignment.
For Subgraph Isomorphism, a common mistake is unconditionally generating K_k without checking k <= |V|. If k is encoded in binary and much larger than |V|, generating K_k would take exponential time.
Students sometimes assume BIG-IS is NP-hard because Independent Set is. The fixed budget of |V| - 1 makes the problem fundamentally easier, with only |V| candidate sets.
Expect to be given a new graph problem and asked to prove it NP-complete. The two-part structure (in NP + NP-hard) is always the same.
The Dominating Set reduction is a model for gadget-based reductions from 3SAT. Understand the role of each gadget component.
For Subgraph Isomorphism, note the edge case handling (k > |V|). Exam reductions often require similar boundary checks.
BIG-IS tests whether you can recognise when a problem that resembles an NP-complete one is actually in P. The answer is always a polynomial-time algorithm.
True or False: Every dominating set is a vertex cover. (False.)
Fill in the blank: In the 3SAT to Dominating Set reduction, k = ______. (n, the number of variables)
True or False: BIG-IS is NP-complete. (False, it is in P.)
True or False: CLIQUE <=p Subgraph Isomorphism via mapping (G, k) to (G, K_k). (True, with the k <= |V| guard.)
Q: Why does the Dominating Set reduction require alpha_i and beta_i in each variable gadget?
A: Without them, the dominating set could avoid the variable gadget entirely (e.g. by using a clause vertex to cover nearby nodes). Alpha_i and beta_i are not adjacent to any clause vertex, so covering them requires at least one of T_i or F_i. Since alpha_i and beta_i are not adjacent to each other, the covering vertex must be T_i or F_i (not alpha_i or beta_i).
Q: Why is BIG-IS in P while IS is NP-complete?
A: IS allows an arbitrary budget k, which can force exponentially many candidate sets. BIG-IS fixes k = |V| - 1, leaving only |V| candidate subsets (one per vertex removed). Checking each takes O(|V|^2), so the total is O(|V|^3).
Q: In the CLIQUE to Subgraph Isomorphism reduction, why do we need special handling for k > |V|?
A: If k > |V|, no clique of size k can exist, so (G, k) is a "no" instance. Generating K_k when k > |V| could take exponential time (k is encoded in binary). The reduction maps to a fixed "no" instance of Subgraph Isomorphism instead.
Dominating Set builds on the 3SAT to Vertex Cover reduction from lecture, adapting the gadget structure. Subgraph Isomorphism builds on the CLIQUE NP-completeness result. BIG-IS connects back to the fundamental question: when does a parameter value collapse a hard problem into an easy one? This idea reappears in approximation algorithms and parameterised complexity.
Dominating set, vertex cover, NP-complete, NP-completeness proof, 3SAT reduction, variable gadget, clause vertex, subgraph isomorphism, graph isomorphism, clique, complete graph K_k, independent set, BIG-IS, polynomial-time algorithm, EECS 376 HW 7, Karp reduction, gadget construction, NP membership, verifier construction