Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 38 / 4

P is the class of decision problems decided by a deterministic algorithm in time polynomial in the encoded input length. NP is the class whose yes-instances have complexity certificates of polynomial length that a deterministic algorithm verifies in polynomial time.

A decision problem is NP-complete if it belongs to NP and is NP-hard: every problem in NP admits a polynomial-time many-one reduction to it. Such a reduction maps an instance $I$ to an instance $R(I)$ in polynomial time and satisfies $I$ is a yes-instance if and only if $R(I)$ is a yes-instance. Membership in NP and NP-hardness are both required.

Run Breadth-first search separately in every component of the undirected graph. Give a starting vertex colour zero and each newly discovered neighbour the opposite colour. Reject if an edge joins two vertices with the same assigned colour; otherwise accept after all components have been explored.

If the algorithm accepts, its assignments constitute a graph colouring with two colours. If it rejects, the two search-tree paths and the conflicting edge contain an odd cycle, on which alternating two colours cannot close consistently. Equivalently, a valid graph colouring with two colours fixes the parity of every path from a component's root, so the detected conflict is impossible in a two-colourable graph. The Breadth-first search work is $O(|V|+|E|)$ with adjacency lists. ThereforeThis is also the two-colourability criterion for bipartite graphs.

The displayed graph consists of three graph triangles sharing the vertex $v$. In a graph colouring with three colours, every graph triangle uses all three colours. The edge $tf$ and the edges $tv,fv$ therefore force $c(t),c(f)$ to be the two colours different from $c(v)$. Likewise the graph triangle $vxy$ forces $c(x),c(y)$ to be those same two colours. The third graph triangle imposes no further restriction on these four vertices. HenceBoth two-element sets and their union have cardinality two. This is a Boolean-pair colouring gadget: after fixing a palette graph triangle, the pair $x,y$ encodes opposite truth values.

Name the upper graph triangle's vertices $a,b,c$, where $b$ is adjacent to $x$ and $c$ to $y$. Name the middle left vertex $d$ and the lower right vertex $e$. Then $a$ is adjacent to $d$, the lower graph triangle is $d,t,e$, and $e$ is adjacent to $z$.

Suppose $x,y,z$ all have colour $F$, while $t$ has a different colour $T$; denote the third colour by $B$. In the upper graph triangle, $b$ and $c$ cannot have colour $F$ and are adjacent, so they have colours $T,B$ in some order and $a$ has colour $F$. In the lower graph triangle, $e$ is adjacent to both $t$ and $z$, forcing $e$ to have colour $B$, and then $d$ must have colour $F$. But the edge $ad$ now has equal-coloured endpoints, a contradiction. ThusFor the three-colour clause gadget used in a reduction, one also needs the converse extension property for Boolean-coloured inputs. With $t=T$ and $x,y,z\in \{T,F\}$, every tuple other than $(F,F,F)$ extends. If $x=T$, take $(a,b,c,d,e)=(T,F,B,F,B)$; this works regardless of $y,z$. If $x=F,y=T$, take $(T,B,F,F,B)$. Finally, if $x=y=F,z=T$, take $(F,T,B,B,F)$. Each assignment satisfies every edge. Therefore this three-colour clause gadget realizes exactly a three-input disjunction on Boolean inputs.

The three-colourability problem belongs to NP: a colour assignment is a polynomial-length complexity certificate, and all edges can be checked in $O(|V|+|E|)$ time.

For NP-hardness, reduce 3-SAT to the three-colourability problem. Start with a palette graph triangle with vertices $T,F,B$. Its colours are necessarily distinct, and name them by these vertices. For each Boolean variable $u$, add vertices $u,\bar{u}$, join them to each other, and join each to $B$. The graph triangle $B,u,\bar{u}$ is the forcing component of the Boolean-pair colouring gadget, so the two literal vertices receive opposite colours $T,F$.

For each Boolean clause, attach a fresh copy of the three-colour clause gadget, identify its $t$ with the palette vertex $T$, and identify its three input vertices with the Boolean clause's Boolean literal vertices. Copies share only palette or literal vertices. A Boolean clause with one or two Boolean literals is padded to three by repeating a literal; an empty Boolean clause can be mapped immediately to the uncolourable graph $K_4$.

Any graph colouring with three colours gives a truth assignment by reading colour $T$ as true. The three-colour clause gadget forbids three false inputs, so every Boolean clause is satisfied. Conversely, any satisfying truth assignment colours the literal pairs, and the extension property proved above independently colours the fresh auxiliary vertices of each clause. Thus the entire graph is three-colourable exactly when the formula is satisfiable.

There are $3+2n+5m$ vertices for $n$ variables and $m$ nonempty padded clauses, and $O(n+m)$ edges. The construction is a polynomial-time many-one reduction. Using the permitted NP-completeness of 3-SAT, we obtain