E ExamMaster

CS Core & Software Engineering · Data Structures & Algorithms

NP-Complete Graph Problems

Clique, chromatic-number and TSP as decision problems, the complement reduction between clique and independent set, and what NP-completeness licenses.

Five concepts on the syllabus graph problems as decision questions — clique and its certificate, the complement reduction to independent set, chromatic number (2 in P, 3 NPC), TSP-decision, and what an NPC proof does and does not license. The four-city tour of cost 18 is the same instance as branch and bound.

  • CS Core & Software Engineering
  • Hard level
  • 5 concepts

1Clique-decision is in NP

A clique is a set of vertices in which every pair is joined by an edge. Clique-decision asks: given an undirected graph G and an integer k, does G contain a clique of size k? That is a yes/no question. A yes-instance has a certificate — a list of k vertices — and the verifier checks that all \binom{k}{2} pairs are edges. That check is polynomial in the size of G, so the problem is in NP.

The problem is also NP-complete (Karp). This concept pins the definition and the certificate. The complement reduction to independent set is a map you can recompute by hand.

Figure. Triangle ABC is a clique of size 3. D hangs off A only, so ABCD is not a clique — BD and CD are missing.

Verify a claimed clique

  1. Read the certificateA list of k distinct vertices.
  2. Check every pairFor each pair, test that the edge is present. \binom{k}{2} tests.
  3. Accept or rejectAccept only if every pair is an edge. A no-instance has no list that passes.

Triangle plus a pendant

Vertices A, B, C, D. Edges AB, BC, CA, AD. Is there a clique of size 3? Of size 4? How many pairs does a 3-vertex certificate force the verifier to check?

  • {A,B,C} pairs AB, BC, CAall three edges present → clique of size 3
  • {A,B,C,D} also needs BD, CDboth missing → no clique of size 4
  • \binom{3}{2}3 edge checks for a size-3 certificate

Pro tip. The verifier does not try other triples. It only checks the list it was given. Search is the solver's job, not the verifier's.

Clique-decision is in NP because
  1. A list of k vertices can be checked for all pairs adjacent in polynomial time
  2. Every graph has a clique, so the answer is always yes
  3. Finding the clique is O(n+m) by BFS

The certificate is the vertex list. Not every graph has a clique of a given k (the size-4 question on this instance is no). BFS does not find a k-clique in polynomial time for arbitrary k.

2Clique in G is independent set in the complement

The complement \overline{G} has the same vertices as G and exactly the edges G is missing (no self-loops). A set S is a clique in G if and only if S is an independent set in \overline{G}: every pair that was present in G is absent in \overline{G}, so no two vertices of S are adjacent there.

Building \overline{G} from G takes O(n^2) time. That map is a polynomial reduction in both directions: (G,k) is a yes for clique if and only if (\overline{G},k) is a yes for independent set. So the two decision problems are NP-complete together — prove one, and the complement gives you the other.

Figure. Left: G with triangle ABC and pendant AD. Right: the complement, which has only BD and CD. {A,B,C} is a clique on the left and an independent set on the right.

Reduce clique to independent set

  1. InputA clique instance (G,k).
  2. ComplementWrite down \overline{G} — one pass over all vertex pairs.
  3. OutputThe independent-set instance (\overline{G},k). Same k.

Complement of the triangle-plus-pendant

G has vertices A, B, C, D and edges AB, BC, CA, AD. Which edges does \overline{G} have, and which size-3 set is independent in \overline{G}?

  • possible pairs among 4 vertices6: AB, AC, AD, BC, BD, CD
  • edges of GAB, BC, CA, AD
  • edges of \overline{G}BD, CD only
  • {A,B,C} in \overline{G}AB, AC, BC are all in G, so none are in the complement → independent set of size 3

Pro tip. {A,B,C} was the clique in G, so it must be independent in the complement. {B,C,D} is not: CD is an edge of \overline{G}.

A clique of size k in G is
  1. An independent set of size k in \overline{G}
  2. A clique of size k in \overline{G} as well
  3. An independent set of size k in G itself

Complement flips edges, so a complete subgraph becomes an empty subgraph. The same set is not a clique in both G and its complement (unless k \le 1). An independent set in G is a clique in the complement, the other direction.

3Chromatic-number decision: 2 is easy, 3 is NPC

A proper k-colouring assigns each vertex one of k colours so that every edge has two colours. Chromatic-number decision asks: given G and k, does such a colouring exist? Equivalently, is \chi(G) \le k? The problem is in NP: the certificate is the colour of each vertex, and the verifier checks each edge.

The k=2 case is in P. A graph is 2-colourable if and only if it is bipartite, and BFS (or DFS) 2-colours each component or reports an odd cycle. For every fixed k \ge 3 the decision problem is NP-complete. 'Graph colouring is NP-complete' on a syllabus means that k \ge 3 statement, not the bipartite test.

Figure. A triangle needs three colours — one per vertex. That is a 3-colouring yes and a 2-colouring no. The NPC statement is 3-colouring on arbitrary graphs, not this one picture.

Place the k

  1. k = 1Yes only if the graph has no edges.
  2. k = 2Bipartite check — in P.
  3. k \ge 3NP-complete. A triangle needs 3; that does not make the general 3-colouring problem easy.

Triangle versus a path

Is the triangle ABC 2-colourable? 3-colourable? Is the path A–D 2-colourable?

  • triangle ABC, k=2no — three pairwise adjacent vertices, odd cycle
  • triangle ABC, k=3yes — give A, B, C three different colours
  • path A–D, k=2yes — colour A one colour, D the other

Pro tip. A single triangle is a tiny yes-instance of 3-colouring and a no-instance of 2-colouring. The NPC claim is about arbitrary graphs, not about K_3.

2-colouring a graph is
  1. In P — equivalent to testing bipartiteness
  2. NP-complete, like 3-colouring
  3. Undecidable

Bipartite graphs are exactly the 2-colourable graphs, and the test is linear-time. 3-colouring is NPC. Colouring is decidable: try all k^n assignments if you must.

4TSP-decision: a tour of cost at most K

TSP-decision asks: given n cities, a distance for every pair, and a budget K, is there a tour — a cycle that visits each city once and returns — whose total distance is at most K? The certificate is a cyclic order of the n cities. The verifier looks up n edge weights, adds them, and compares with K. That is polynomial, so the problem is in NP.

It is NP-complete. The four-city instance from branch and bound is a yes for K=18 and a no for K=17. Those two answers are not a proof of completeness; they are what a certificate looks like on a graph you can add by hand.

Figure. Certificate 1,2,4,3 on the four-city instance: edges 2, 4, 3, 9 sum to 18. Accept for K=18; reject this certificate for K=17.

Verify a claimed tour

  1. Read the orderA permutation c_1,\ldots,c_n of the cities.
  2. SumAdd d(c_1,c_2)+\cdots+d(c_{n-1},c_n)+d(c_n,c_1).
  3. CompareAccept if the sum is \le K and the permutation used each city once.

K = 17 and K = 18

Distances: 1-2=2, 2-4=4, 4-3=3, 3-1=9, and the other pairs as in the branch-and-bound table. Verify the certificate 1,2,4,3 against K=18 and against K=17.

  • 2+4+3+918
  • 18 \le 18?yes — accept for K=18
  • 18 \le 17?no — this certificate fails for K=17
  • any tour \le 17?no — the shortest tour is 18, so K=17 is a no-instance

Pro tip. A failed certificate does not prove a no-instance. The no for K=17 uses the separate fact that every tour is at least 18. The verifier alone never proves a no.

A polynomial-time verifier for TSP-decision is given
  1. A cyclic order of the cities, and it only adds n edge weights
  2. Nothing — it must find the shortest tour itself
  3. A claimed optimum value, with no tour

The certificate is the tour. Finding the tour is the solver's job. A bare number with no order cannot be checked against the edges.

5What NP-completeness licenses — and what it does not

A proof that a decision problem is NP-complete is a licence to stop looking for a polynomial algorithm that works on every instance, unless you are also trying to prove P = NP. It is not a licence to call a 12-city TSP 'impossible', and it is not a claim that every heuristic is wrong.

Honest tools after an NPC proof: exact exponential methods that are fine for small n (branch and bound, Held–Karp-style DP, SAT solvers), algorithms that exploit structure (bipartite, planar, bounded k), and approximation or heuristic methods when a decision budget K is replaced by a search for a good object. Branch and bound on the four-city tour is the first of those, not a contradiction of NP-completeness.

Figure. Qualitative 'do this / don't chase that' sketch, not a runtime. The terracotta bar is the P = NP claim, not a recommended tool.

After an NPC proof

  1. Do not chase a general poly-time solverThat chase is a P = NP claim.
  2. Do solve small or structured instancesExact search, special-case algorithms, ILP / SAT encodings.
  3. Do name the questionDecision with a K versus optimisation. Approximation talks to the second.
Licensed responses
ResponseLicensed?
Give up on a general poly-time algorithmYes
Call every 15-vertex instance unsolvableNo
Use B&B / DP / SAT on small nYes
Use 2-colouring for k=2Yes — that case is in P
Treat TSP-opt as NPCNo — it is NP-hard, not a language
NP-completeness of TSP-decision means
  1. A general poly-time algorithm would prove P = NP; small instances can still be solved exactly
  2. No computer can ever find a tour of 8 cities
  3. Branch and bound is incorrect, because the problem is hard

Hardness is about all instances and polynomial time. Eight cities are 7! tours from a fixed start — enumerable. Branch and bound is an exact exponential method, not a mistaken P algorithm.

Notes

  • Clique-decision: given G and k, does G contain k pairwise-adjacent vertices? In NP via the vertex list as a certificate; NP-complete (Karp).
  • Independent-set decision is equivalent: a set is a clique in G if and only if it is independent in the complement \overline{G}. That is a polynomial reduction you can check by hand.
  • Chromatic-number decision: given G and k, can the vertices be coloured with k colours so that every edge is bichromatic? 2-colouring is in P (bipartite check). For k \ge 3 the decision problem is NP-complete.
  • TSP-decision: given a complete weighted graph and a budget K, is there a tour of cost \le K? Certificate is the cyclic order of cities. NP-complete.
  • These are decision problems. The optimisation twins — largest clique, \chi(G), shortest tour — are NP-hard and were placed in the previous topic.
  • NP-completeness does not say a 10-vertex instance is hopeless. It says there is no known poly-time algorithm that works for every instance, so exact search (branch and bound, DP) or structure-exploiting algorithms are the honest tools.

Formulas

  • Clique of size k in G \iff independent set of size k in \overline{G}.
  • Building \overline{G} from G is O(n^2) — a polynomial reduction.
  • \chi(G) \le 2 \iff G is bipartite, decidable in O(n+m) by BFS 2-colouring.
  • \chi(G) \le k for k \ge 3 is NP-complete.
  • TSP-decision certificate: a cyclic permutation; verifier sums n edge weights and compares with K.

Exam traps & shortcuts

  • When the syllabus says clique / chromatic number / TSP are NP-complete, it means the decision versions with a k or a K.
  • 2-colouring is not a counter-example to 'colouring is NPC' — the NPC statement starts at 3 colours.
  • A complete graph K_n has a clique of size n and needs n colours. A triangle-free graph can still have large chromatic number, but that fact is not needed to see that 3-colouring is already hard.
  • Do not invent a SAT-to-clique gadget in an exam unless you can draw every clause vertex. The complement reduction is the one you can finish.

Reference tables

Certificate and the easy special case, restated from the concepts.

Three decision problems
ProblemYes-questionCertificateEasy case
CliqueClique of size k?k vertices, all pairs edgesk \le 2 is poly-time
Chromatic number\chi(G) \le k?A k-colouringk \le 2 is bipartite / in P
TSP-decisionTour of cost \le K?A cyclic orderMetric / tiny n still exponential in the worst case

The reduction you can finish by hand.

Complement identities
In GIn \overline{G}
Clique of size kIndependent set of size k
Independent set of size kClique of size k
Edge uvNo edge uv

Recap

Night-before graph-NPC pegs.

Clique
k pairwise-adjacent vertices. Certificate = the k names. NPC.
Complement
Clique in G \iff independent set in \overline{G}. O(n^2) reduction.
Colour
k=2 is bipartite (P). k\ge 3 is NPC.
TSP-dec
Tour \le K? Certificate = cyclic order. This instance: yes at 18, no at 17.
License
Stop chasing a general P algorithm. Still solve small n; still use 2-colouring.

Practise NP-Complete Graph Problems

Reading is free and needs no account. Practice, mocks and progress live in the app.

  • A 5-question practice set that ends the chapter
  • 5 quick checks with worked explanations
  • Timed mocks scored with the real marking scheme
  • Readiness tracked per topic, kept on your device
Continue with Google — freeNo card, no trial. Works offline once installed.