Skip to content

20. Complexity and intractable problems

[Source: include/ADS/complexity/Problems.h, Nondeterminism.h, Domino.h, Reductions.h, EasyCases.h; include/ADS/intractable/Pseudopolynomial.h, Approximation.h, BranchAndBound.h, Heuristics.h, FifteenPuzzle.h]

We are concerned in this chapter with the problems for which no algorithm of polynomial time is known, and with what one can do about them. The headers of ADS/complexity follow chapter 18 of Montresor 2025: they give each problem of the class NP its certificate and an enumeration that decides it in exponential time, simulate the nondeterministic algorithms, realize the polynomial reductions that make a chain of NP-complete problems, and solve a few problems close to them in polynomial time. Those of ADS/intractable follow its chapter 19, i.e., the ways of facing a problem that is NP-hard, each of which gives up one of three things (the time polynomial in the size of the input, the optimality of the solution, or the generality of the instances). We organize the chapter as follows. Sections 20.1 to 20.5 are devoted to the theory: the classes P and NP and the certificates, the nondeterminism and its simulation, the enumerations, the reductions, and the polynomial cases. Sections 20.6 to 20.10 are devoted to the strategies, in the order of the book: the pseudopolynomial algorithms, the approximations, the branch-and-bound, the heuristics and the search of the fifteen puzzle. Throughout the chapter \(n\) is the number of the nodes, the cities, the objects or the variables of an instance, and the words in small capitals of the book are written in capitals (e.g., CLIQUE). In the sets of §1.9, the headers of this chapter are all base.

20.1 Problems, certificates and the classes P and NP

A decision problem \(\Pi\) is a set of instances, each with the answer YES or NO, and \(Y_\Pi\) is the set of the instances whose answer is YES. The problems of optimization (the largest clique, the shortest tour) become decision problems by a bound \(k\) on the value (whether a clique of \(k\) nodes exists), which is as hard up to a polynomial factor, since a binary search on \(k\) finds the optimum with a logarithmic number of questions. As usual, the size \(\lvert x \rvert\) of an instance is the length of a "reasonable" encoding of it, with the numbers written in binary; hence a number \(k\) counts \(\Theta( \log k )\) instead of \(k\), which is the distinction on which the pseudopolynomial algorithms of §20.6 rest. Then the class P holds the problems decided by an algorithm in time \(O( \lvert x \rvert^c )\) for a constant \(c\). The class NP holds those that have a polynomial certificate, i.e., a polynomial \(p\) and an algorithm \(V\) of polynomial time such that

\[ x \in Y_\Pi \iff \exists \, y : \ \lvert y \rvert \le p( \lvert x \rvert ) \ \text{and} \ V( x , y ) = \text{YES} \tag{20.1} \]

(Montresor 2025, §18.1). The functions cliqueCertificate(), tspCertificate(), satCertificate() of Problems.h and legalTiling() of Domino.h are such algorithms \(V\), and so are the postconditions of the other enumerations of Problems.h, each with a certificate of polynomial size (a set of nodes, a tour, an assignment, a covering); hence each problem of the area is in NP. Also, \(\mathrm{P} \subseteq \mathrm{NP}\), since a polynomial algorithm is a checker that ignores \(y\); whether the inclusion is strict is, as is well known, open.

We now fix the representations that the headers share. A graph is an Adjacency, i.e., a square matrix of bool, symmetric when the graph is unoriented, whose diagonal (a loop of a node) each problem ignores: a node with a loop may be in an independent set, need not be in a cover, and takes a color like any other. A formula in conjunctive normal form is a Cnf, a vector of clauses, each a Clause, i.e., a vector of literals, \(+( v + 1 )\) for the variable \(v\) and \(-( v + 1 )\) for its negation; a set of nodes, a path or a tour is a Nodes, a vector of int; and a system of 0-1 integer programming is \(A x \le b\). Also, the contracts check that the graphs are square (and symmetric where the problem is unoriented), that the literals name the variables of the formula and that the numbers of the numerical problems are not negative, and each certificate returned by an enumeration is checked as a postcondition.

20.2 Nondeterminism

A nondeterministic algorithm may call choice( k ), which returns one of \(k\) alternatives, and it ends with success or failure; it answers YES on \(x\) if some sequence of choices leads to success, and its time is that of the longest sequence of choices (Montresor 2025, §18.2). An algorithm of this kind that runs in polynomial time is a certificate in disguise: the sequence of the choices that leads to success is a \(y\) of (20.1), and, conversely, the algorithm that chooses the bits of \(y\) one by one and then runs \(V( x , y )\) succeeds if and only if (20.1) holds. Hence NP is also the class of the problems decided in polynomial time by a nondeterministic algorithm, whence its name.

In Nondeterminism.h, a nondeterministic algorithm is a function that receives a Chooser and calls its choice( k ), returning true for success and false for failure. Internally, the Chooser keeps the sequence \(P\) of the pairs (choice, number of alternatives) of the current run and the number \(t\) of the choices made in it (Algorithm 20.1). A choice at a depth reached for the first time is 0, and one at a depth already in \(P\) repeats the choice stored there. The function run( alg ) replays the algorithm on each sequence of choices in lexicographic order, and stops at the first success; after a failure, it drops from \(P\) the choices of the run beyond the depth reached and, from the end, those that have no alternative left, and it advances the last one that has (Figure 20.1). This is the visit in depth of the tree of the choices with a backtrack on the last choice still open (Montresor 2025, §18.3).

Figure 20.1. The sequence of the pairs (choice, alternatives) of a Chooser after a run that made three choices and failed, and before the next run: the last two pairs have no alternative left and are dropped, and the first one is advanced.

Algorithm 20.1. The choice of a Chooser, and the simulation of a nondeterministic algorithm by the enumeration of its sequences of choices (Montresor 2025, §18.3).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{choice}( k )\quad \triangleright\ P \text{ the pairs (choice, arity) of the run, } t \text{ the next} \cr 2 & \quad \textbf{if}\ t = |P|\ \textbf{then}\ \text{append } ( 0 , k ) \text{ to } P\quad \triangleright\ \text{a new choice starts from } 0 \cr 3 & \quad t \gets t + 1;\ \textbf{return}\ \text{the choice of } P[ t ] \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{run}( \mathit{alg} )\quad \triangleright \ \text{the runs in the lexicographic order of their choices} \cr 2 & \quad P \gets () \cr 3 & \quad \textbf{loop} \cr 4 & \qquad t \gets 0;\ \textbf{if}\ \mathit{alg}() \ \textbf{then return true} \cr 5 & \qquad \text{keep the first } t \text{ pairs of } P \text{, then drop from its end the pairs } ( k - 1 , k ) \text{ already at their last choice} \cr 6 & \qquad \textbf{if}\ P = ()\ \textbf{then return false}\quad \triangleright\ \text{every run failed} \cr 7 & \qquad \text{raise by one the choice of the last pair of } P \end{array} \]

Lemma 20.1 (the simulation). A nondeterministic algorithm that makes at most \(h\) choices of at most \(k\) alternatives each, in time \(t\), is simulated by run() in time

\[ O( k^h \, t ) . \tag{20.2} \]

Proof. The sequences of choices are the paths from the root of a tree of height at most \(h\) whose nodes have at most \(k\) children, and the tree has at most \(k^h\) leaves. Each run follows one path, in time \(O( t )\), and the next sequence differs from the last one in a suffix. Hence the runs are at most \(k^h\), and the bookkeeping of \(P\) costs \(O( h ) = O( t )\) per run. \(\square\)

With \(h\) and \(t\) polynomial in \(\lvert x \rvert\), (20.2) is \(2^{O( \lvert x \rvert^c )}\); hence \(\mathrm{NP} \subseteq \mathrm{EXP}\), and no simulation essentially faster than the visit of the tree is known for the NP-complete problems of §20.4. If a pointer runs is given, run() counts there the runs that it makes, which a test uses to observe the bound (20.2); choices() returns the sequence of the successful run after a YES, i.e., the certificate.

20.3 Certificates and enumerations

In fact, the enumerations of Problems.h and squareTiling() of Domino.h are (20.2) specialized to each problem: a backtrack builds the certificate one piece at a time and checks each partial certificate, so that a subtree whose root already fails the check is skipped. Its tree of the choices is that of the subsets, of the permutations or of the functions of the problem, and Table 20.1 gives its size, i.e. (cf. (20.2)), the time in the worst case up to the polynomial cost of a node, which is typically "small".

Table 20.1. The enumerations of ADS/complexity and the trees of their choices; \(m\) is the number of the processors, or of the tiles, and \(Y\) the family of the 3-sets.

Problem Function Certificate Leaves of the tree
CLIQUE, INDEPENDENT SET clique(), independentSet() \(k\) nodes \(\binom{n}{k}\)
VERTEX COVER vertexCover() at most \(k\) nodes \(\sum_{s \le k} \binom{n}{s}\)
GRAPH COLORABILITY coloring() a color per node \(k^n\)
BISECTION bisection() \(n / 2\) nodes, 0 among them \(\binom{n - 1}{n / 2 - 1}\)
TRAVELING SALESMAN, the Hamiltonian problems tsp(), hamiltonianCircuit(), and so on a permutation \(( n - 1 )!\) or \(n!\)
LONGEST PATH longestPath() a simple path \(O( ( n - 1 )! )\)
DEGREE-CONSTRAINED SPANNING TREE boundedSpanningTree() \(n - 1\) edges at most \(2^{\lvert E \rvert}\)
SATISFIABILITY, 0-1 INTEGER PROGRAMMING satisfiable(), lp01() a 0-1 vector \(2^n\)
SUBSET SUM, PARTITION, KNAPSACK subsetSumExists(), partition(), knapsackDecision() a subset \(2^n\)
MULTIPROCESSOR SCHEDULING multiprocessorScheduling() a processor per program \(m^n\)
EXACT COVER BY 3-SETS, 3-DIMENSIONAL MATCHING exactCover3(), threeDimensionalMatching() a subset of the sets \(2^{\lvert Y \rvert}\)
BOUNDED TILING squareTiling() a tile per square \(m^{n^2 - 1}\)

Graphs. The function clique() (the enCricca() of the book) lists the sets of \(k\) nodes in increasing order, and extends a set only by a node adjacent to all of it; independentSet() is the same enumeration with the test negated, and vertexCover() lists the sets by increasing size up to \(k\) (Algorithm 20.2). Note that the enumeration of the sets stops extending a partial set when the nodes left cannot complete it to \(k\) nodes. The function coloring() (exercise 18.6) colors the nodes in order, and numbers the colors in the order of their first use, so that two colorings that differ by a renaming of the colors are not both tried; bisection() looks for the halves of \(n / 2\) nodes that contain the node 0, so that each partition is tried once, and cut by at most \(k\) edges. The certificate cliqueCertificate() (the certificatoCricca() of the book) checks in \(O( \lvert S \rvert^2 )\) that the set \(S\) has distinct nodes, at least \(k\) of them, all adjacent.

Algorithm 20.2. The certificate of CLIQUE, and the enumerations of CLIQUE, INDEPENDENT SET, VERTEX COVER, GRAPH COLORABILITY and BISECTION (Montresor 2025, chapter 18 and exercise 18.6).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{cliqueCertificate}( G , S , k )\quad \triangleright\ O( |S|^2 ) \cr 2 & \quad \textbf{return}\ k \le |S| \text{ and every two places } a < b \text{ of } S \text{ hold distinct nodes with } G[ S[ a ] ][ S[ b ] ] \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{clique}( G , k ) \cr 2 & \quad \textbf{return}\ \emptyset \text{ if } k \le 0 \text{, else } \mathrm{choose}( \emptyset , 0 ) \cr 3 & \textbf{function}\ \mathrm{choose}( S , i )\quad \triangleright\ S \text{ a clique of nodes before } i \cr 4 & \quad \textbf{if}\ |S| = k\ \textbf{then return}\ S \cr 5 & \quad \textbf{if}\ k - |S| > n - i\ \textbf{then return nil}\quad \triangleright\ \text{not enough nodes left} \cr 6 & \quad \textbf{foreach}\ v \in [ i , n ) \text{ adjacent to every node of } S \text{, in increasing order} \ \textbf{do} \cr 7 & \qquad R \gets \mathrm{choose}( S \cup \{ v \} , v + 1 ); \ \textbf{if}\ R \ne \textbf{nil}\ \textbf{then return}\ R \cr 8 & \quad \textbf{return nil} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{independentSet}( G , k ) \cr 2 & \quad \textbf{return}\ \text{as } \mathrm{clique}( G , k ) \text{, a node } v \text{ being added when it is adjacent to no node of } S \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{vertexCover}( G , k )\quad \triangleright \ \text{the smallest first} \cr 2 & \quad \textbf{foreach}\ S \subseteq V \text{, by size } 0 , 1 , \ldots , \min\{ k , n \} \text{ and then in lexicographic order} \ \textbf{do} \cr 3 & \qquad \textbf{if}\ \text{every edge has an end in } S \ \textbf{then return}\ S \cr 4 & \quad \textbf{return nil} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{color}( u )\quad \triangleright\ c[ 0 .. u - 1 ] \text{ a proper coloring, from } u = 0 \cr 2 & \quad \textbf{if}\ u = n\ \textbf{then return true} \cr 3 & \quad \mathit{used} \gets \text{the number of the colors on } 0 , \ldots , u - 1 \text{, i.e., } 1 + \max_{v < u} c[ v ] \text{ or } 0\quad \triangleright\ \text{colors in order} \cr 4 & \quad \textbf{foreach}\ x \in [ 0 , \min\{ k , \mathit{used} + 1 \} ) \text{ on no neighbor } v < u \text{ of } u\ \textbf{do}\quad \triangleright\ \text{one new color at most} \cr 5 & \qquad c[ u ] \gets x;\ \textbf{if}\ \mathrm{color}( u + 1 ) \ \textbf{then return true} \cr 6 & \quad \textbf{return false} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{bisection}( G , k )\quad \triangleright\ 0 \in S \text{ breaks the symmetry of the two halves} \cr 2 & \quad \textbf{if}\ n \text{ is odd}\ \textbf{then return nil} \cr 3 & \quad \textbf{return}\ \text{the first } S \ni 0 \text{ of } n / 2 \text{ nodes crossed by at most } k \text{ edges, or } \textbf{nil} \end{array} \]

Tours and paths. The function tsp() (the enTsp() of the book) lists the permutations that start with the city 0, which breaks the symmetry of the rotations, and does not extend a partial tour longer than \(k\) (Algorithm 20.3); the pruning is correct only for distances not negative, which are a precondition (adding a constant \(c\) to all the distances and \(n c\) to \(k\) keeps the answer, and makes them so). Also, the four Hamiltonian problems share one backtracking, hamilton( P ), which extends a path by the nodes adjacent to its last one, in increasing order. It runs as hamiltonianCircuit() from \(P = ( 0 )\) and closed, hamiltonianCycle() on the oriented edges (exercise 18.12), hamiltonianPath() from each possible start, or from a given \(r\) to a given \(t\) (exercise 18.13), and hamiltonianChain() on the unoriented edges (exercise 18.14). The function longestPath() (exercise 18.15) looks for a simple path from \(r\) to \(t\) of at least \(k\) edges, and does not extend a path that reaches \(t\) too short, since it could not come back to \(t\). On an acyclic graph the same problem is polynomial: longestPathDag() computes the longest path by one scan of the nodes in topological order (a path never comes back to a node already scanned), in \(O( n^2 )\) on the matrix. The function boundedSpanningTree() (exercise 18.16) takes each edge and then leaves it, in order, never taking an edge that closes a cycle or exceeds a degree \(k\), and stops when the edges left cannot complete a tree.

Algorithm 20.3. The certificate and the enumeration of TRAVELING SALESMAN, the backtracking of the Hamiltonian problems, and the paths and the trees of exercises 18.12 to 18.16.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{tspCertificate}( D , k , P ) \cr 2 & \quad \textbf{return}\ P \text{ is a permutation of the cities and the circuit } P[ 0 ] , \ldots , P[ n - 1 ] , P[ 0 ] \text{ costs } \le k \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{extend}( S , \ell )\quad \triangleright\ S \text{ a path from } 0 \text{ of length } \ell \text{, from } ( ( 0 ) , 0 ) \cr 2 & \quad \textbf{if}\ k < \ell\ \textbf{then return false}\quad \triangleright\ \text{the costs are not negative} \cr 3 & \quad \textbf{if}\ |S| = n\ \textbf{then return}\ \ell + D[ S[ n - 1 ] ][ 0 ] \le k \cr 4 & \quad \textbf{return}\ \text{whether } \mathrm{extend}( S \cdot ( c ) , \ell + D[ S[ |S| - 1 ] ][ c ] ) \text{ holds for a } c \notin S \text{, tried by increasing } c \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{hamilton}( P )\quad \triangleright\ P \text{ a path of } G \cr 2 & \quad \textbf{if}\ |P| = n\ \textbf{then return}\ ( P \text{ ends at } \mathit{end} \text{, if given} ) \text{ and } ( \text{an edge closes it, if } \mathit{closed} ) \cr 3 & \quad \textbf{return}\ \text{whether } \mathrm{hamilton}( P \cdot ( v ) ) \text{ holds for a } v \notin P \text{ after the last node of } P \text{, by increasing } v \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{hamiltonianCycle}( G )\quad \triangleright\ \text{a cycle passes by } 0 \cr 2 & \quad \textbf{return}\ \textbf{nil} \text{ if } n < 2 \text{, else } \mathrm{hamilton}( ( 0 ) ) \text{, closed and with no end} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{hamiltonianPath}( G , r , t )\quad \triangleright\ r , t \text{ the ends, } -1 \text{ if free} \cr 2 & \quad \textbf{foreach}\ \text{start } s \text{, only } r \text{ if } r \ge 0\ \textbf{do}\ \textbf{if}\ \mathrm{hamilton}( ( s ) ) \text{, open and ending at } t \text{, finds } P \ \textbf{then return}\ P \cr 3 & \quad \textbf{return nil} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{hamiltonianChain}( G )\quad \triangleright\ G \text{ unoriented: a symmetric matrix} \cr 2 & \quad \textbf{return}\ \mathrm{hamiltonianPath}( G , -1 , -1 ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{extend}( P )\quad \triangleright\ P \text{ a simple path from } r \text{, from } P = ( r ) \cr 2 & \quad \textbf{if}\ P \text{ ends at } t\ \textbf{then return}\ k \le |P| - 1\quad \triangleright\ \text{its edges} \cr 3 & \quad \textbf{return}\ \text{whether } \mathrm{extend}( P \cdot ( v ) ) \text{ holds for a } v \notin P \text{ after the last node of } P \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{longestPathDag}( G , r , t )\quad \triangleright\ L[ v ] \text{ the longest path from } r \text{, } -1 \text{ if none} \cr 2 & \quad L[ v ] \gets -1 \text{ for every node } v;\ L[ r ] \gets 0 \cr 3 & \quad \textbf{foreach}\ u \text{ in a topological order with } L[ u ] \ge 0\ \textbf{do} \cr 4 & \qquad L[ v ] \gets \max\{ L[ v ] , L[ u ] + 1 \} \text{ for each edge } ( u , v ) \cr 5 & \quad \textbf{return}\ L[ t ] \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{extend}( T , i )\quad \triangleright \ \text{the edges } E[ i ] , \ldots , E[ m ] \text{ to decide, from } ( \emptyset , 1 ) \cr 2 & \quad \textbf{if}\ |T| = n - 1\ \textbf{then return true}\quad \triangleright\ \text{a spanning tree of degree} \le k \cr 3 & \quad \textbf{if}\ n - 1 - |T| > m - i + 1 \ \textbf{then return false}\quad \triangleright \ \text{too few edges left, } i > m \text{ included} \cr 4 & \quad [ u , v ] \gets E[ i ] \cr 5 & \quad \textbf{if}\ u , v \text{ have degree } < k \text{ in } T \text{, are in two trees of } T \text{, and } \mathrm{extend}( T \cup \{ [ u , v ] \} , i + 1 )\ \textbf{then return true} \cr 6 & \quad \textbf{return}\ \mathrm{extend}( T , i + 1 ) \end{array} \]

Formulae and numbers. The function satisfiable() assigns the variables in order, and checks a clause as soon as its largest variable is set, which cuts the tree at the first clause made false; satCertificate() checks an assignment in time linear in the size of the formula, and lp01() lists the \(2^n\) vectors of 0-1 integer programming in lexicographic order (Algorithm 20.4). Each numerical problem takes each element and then leaves it: subsetSumExists() does not extend a sum above \(k\), partition() looks for a subset of half the sum, and knapsackDecision() (the enZaino() of the book, exercise 18.5) does not extend a volume above the capacity. The function multiprocessorScheduling() tries each program on each processor on which it fits within the time \(d\), but on one empty processor only, since the empty processors are all equal; it answers NO for \(d < 0\), even with no programs, since an idle processor is loaded 0.

Algorithm 20.4. The certificate and the enumeration of SATISFIABILITY, 0-1 INTEGER PROGRAMMING, and the numerical problems of chapter 18 (Montresor 2025, chapter 18 and exercise 18.5).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{satCertificate}( F , x ) \cr 2 & \quad \textbf{return}\ \text{whether every clause of } F \text{ has a literal true under } x \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{assign}( v )\quad \triangleright\ x[ 0 .. v - 1 ] \text{ fixed, from } v = 0 \cr 2 & \quad \textbf{if}\ \text{a clause whose last variable is } v \text{ is false under } x\ \textbf{then return false}\quad \triangleright\ \text{now fully fixed} \cr 3 & \quad \textbf{if}\ v = n\ \textbf{then return true} \cr 4 & \quad \textbf{foreach}\ b \in ( \textbf{false} , \textbf{true} ) \ \textbf{do}\ x[ v ] \gets b;\ \textbf{if}\ \mathrm{assign}( v + 1 )\ \textbf{then return true} \cr 5 & \quad \textbf{return false} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{lp01}( A , b , n ) \cr 2 & \quad \textbf{return}\ \text{the first } x \in \{ 0 , 1 \}^n \text{ in lexicographic order with } A x \le b \text{, or } \textbf{nil}\quad \triangleright\ 2^n \text{ tries} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{extend}( S , i , s )\quad \triangleright \ s \text{ the sum of } S \text{, from } ( \emptyset , 0 , 0 ) \cr 2 & \quad \textbf{if}\ s = k\ \textbf{then return true} \cr 3 & \quad \textbf{if}\ k < s\ \textbf{or}\ i = n \ \textbf{then return false}\quad \triangleright \ \text{the items are not negative} \cr 4 & \quad \textbf{return}\ \mathrm{extend}( S \cup \{ i \} , i + 1 , s + A[ i ] )\ \textbf{or}\ \mathrm{extend}( S , i + 1 , s )\quad \triangleright\ \text{with } i \text{ first} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{partition}( A )\quad \triangleright \ \text{a subset of half the sum} \cr 2 & \quad s \gets \textstyle\sum_i A[ i ] \cr 3 & \quad \textbf{return}\ \textbf{nil} \text{ if } s \text{ is odd, else } \mathrm{subsetSumExists}( A , s / 2 ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{extend}( S , i , \mathit{tp} , \mathit{tv} )\quad \triangleright\ \text{the profit and the volume of } S \text{, from } ( \emptyset , 0 , 0 , 0 ) \cr 2 & \quad \textbf{if}\ C < \mathit{tv}\ \textbf{then return false}\quad \triangleright\ \text{too heavy} \cr 3 & \quad \textbf{if}\ k \le \mathit{tp}\ \textbf{then return true} \cr 4 & \quad \textbf{if}\ i = n\ \textbf{then return false} \cr 5 & \quad \textbf{return}\ \mathrm{extend}( S \cup \{ i \} , i + 1 , \mathit{tp} + p[ i ] , \mathit{tv} + v[ i ] )\ \textbf{or} \ \mathrm{extend}( S , i + 1 , \mathit{tp} , \mathit{tv} ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{assign}( i )\quad \triangleright \ \text{the jobs before } i \text{ placed, from } i = 0 \text{ and no load} \cr 2 & \quad \textbf{if}\ i = n\ \textbf{then return true} \cr 3 & \quad \textbf{foreach}\ \text{processor } q \text{, in order, with } \mathit{load}[ q ] + t[ i ] \le d\ \textbf{do} \cr 4 & \qquad ( \mathit{load}[ q ] , a[ i ] ) \gets ( \mathit{load}[ q ] + t[ i ] , q );\ \textbf{if}\ \mathrm{assign}( i + 1 ) \ \textbf{then return true} \cr 5 & \qquad \mathit{load}[ q ] \gets \mathit{load}[ q ] - t[ i ] \cr 6 & \qquad \textbf{if}\ \mathit{load}[ q ] = 0 \ \textbf{then return false}\quad \triangleright \ \text{the other empty processors are the same} \cr 7 & \quad \textbf{return false} \end{array} \]

Covers and matchings. The function exactCover3() (the enCopertura() of the book, exercise 18.7) looks for sets of three elements of \(\{ 0 , \ldots , m - 1 \}\) that partition it, taking each set that meets none of those chosen and then leaving it; threeDimensionalMatching() reduces 3-DIMENSIONAL MATCHING to it, by making the three coordinates of the triples disjoint (the triple \(( w , x , v )\) becomes the set \(\{ w , q + x , 2 q + v \}\)). The function bribes() (the mazzette() of the book, exercises 18.1 and 18.4) gives the \(n\) bribes \(M\) to the \(n\) politicians in such a way that the party PS gets twice as much as the party PDF, by the permutations of the bribes in lexicographic order (Algorithm 20.5).

Algorithm 20.5. The exact cover by 3-sets, the 3-dimensional matching, and the bribes (Montresor 2025, exercises 18.1, 18.4 and 18.7).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{extend}( S , j , \mathit{left} )\quad \triangleright\ \mathit{left} \text{ the elements not covered, from } ( \emptyset , 0 , m ) \cr 2 & \quad \textbf{if}\ \mathit{left} = 0\ \textbf{then return true} \cr 3 & \quad \textbf{if}\ j = |Y|\ \textbf{then return false} \cr 4 & \quad \textbf{if}\ Y[ j ] \text{ has three distinct elements, none covered by } S \text{, and} \cr & \qquad \mathrm{extend}( S \cup \{ j \} , j + 1 , \mathit{left} - 3 ) \ \textbf{then return true} \cr 5 & \quad \textbf{return}\ \mathrm{extend}( S , j + 1 , \mathit{left} ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{threeDimensionalMatching}( M , q )\quad \triangleright\ \text{the three sets one after the other} \cr 2 & \quad \textbf{return}\ \mathrm{exactCover3}( ( \{ w , q + x , 2 q + v \} : ( w , x , v ) \in M ) , 3 q ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{bribes}( M , \mathit{ps} )\quad \triangleright\ \text{by enumeration of the permutations} \cr 2 & \quad \textbf{return}\ \text{the first permutation } \pi \text{ of } M \text{ in lexicographic order with} \cr & \qquad \textstyle\sum_{i : \mathit{ps}[ i ]} \pi[ i ] = 2 \textstyle\sum_{i : \textbf{not}\ \mathit{ps}[ i ]} \pi[ i ] \text{, or } \textbf{nil} \end{array} \]

The square tiling. In BOUNDED TILING (the DOMINO LIMITATO of the book), the \(n \times n\) squares of a board are to be covered with copies of \(m\) oriented tiles, each split by its diagonals into four colored quarters, never rotated, with the tile \(d = D[ 0 ]\) in the corner \(( 0 , 0 )\) and touching sides of the same color (Figure 20.2). A Tile holds the colors of its four sides, and the square \(( i , j )\) is the column \(i\) and the row \(j\) from the bottom left; a covering is a Tiling, a matrix whose entry \(( i , j )\) is the index in \(D\) of the tile of that square. The function legalTiling() is the certificate, in \(O( n^2 )\). The enumeration squareTiling() fills the squares by rows from the bottom, and places a tile only if it fits its left and lower neighbours, which prunes the enumeration of the \(m^{n^2 - 1}\) coverings at the first wrong side (Algorithm 20.6).

Figure 20.2. Four tiles, each with the colors of its upper, right, lower and left sides, and a legal covering of the \(2 \times 2\) board with \(d = D[ 0 ]\) in the corner \(( 0 , 0 )\); the touching sides have the same color.

Algorithm 20.6. The certificate and the enumeration of BOUNDED TILING (Montresor 2025, chapter 18).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{legalTiling}( D , n , T )\quad \triangleright\ T[ i ][ j ] \text{ the tile of the square in column } i \text{, row } j \cr 2 & \quad \textbf{if}\ n < 1 \text{, or } T \text{ is not an } n \times n \text{ table of tiles of } D \text{, or } T[ 0 ][ 0 ] \ne 0 \ \textbf{then return false} \cr 3 & \quad \textbf{return}\ \text{whether every two neighbors match:} \cr & \qquad D[ T[ i ][ j ] ].\mathit{right} = D[ T[ i + 1 ][ j ] ].\mathit{left} \text{ and } D[ T[ i ][ j ] ].\mathit{up} = D[ T[ i ][ j + 1 ] ].\mathit{down} \cr & \qquad \text{wherever the second square exists} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{place}( s )\quad \triangleright \ \text{the squares } s = i + j n \text{ by rows, from } s = 0 \cr 2 & \quad \textbf{if}\ s = n^2\ \textbf{then return true} \cr 3 & \quad ( i , j ) \gets ( s \bmod n , \lfloor s / n \rfloor ) \cr 4 & \quad \textbf{foreach}\ \text{tile } t \text{, only } t = 0 \text{ on the first square}\ \textbf{do} \cr 5 & \qquad \textbf{if}\ t \text{ matches the tile on its left, if any, and the one below, if } \text{any}\ \textbf{then} \cr 6 & \qquad\quad T[ i ][ j ] \gets t;\ \textbf{if}\ \mathrm{place}( s + 1 )\ \textbf{then return true} \cr 7 & \quad \textbf{return false} \end{array} \]

We remark that the pruning of the enumerations usually changes the time in practice, but never the bound of Table 20.1: there are instances (e.g., those with no solution and no early failure) on which the tree is visited in full.

20.4 Reductions and NP-completeness

A polynomial reduction of \(A\) to \(B\) is a function \(f\), computable in polynomial time, such that

\[ x \in Y_A \iff f( x ) \in Y_B , \tag{20.3} \]

written \(A \propto B\) (Montresor 2025, §18.4).

Lemma 20.2. The relation \(\propto\) is transitive, and \(A \propto B\) with \(B \in \mathrm{P}\) gives \(A \in \mathrm{P}\).

Proof. An algorithm of polynomial time writes an output of polynomial size, and therefore \(\lvert f( x ) \rvert \le q( \lvert x \rvert )\) for a polynomial \(q\). Hence a polynomial algorithm for \(B\) run on \(f( x )\), and a second reduction applied to \(f( x )\), take time polynomial in \(\lvert x \rvert\), since a polynomial of a polynomial is a polynomial. \(\square\)

A problem is NP-hard if each problem of NP reduces to it, and NP-complete if it is also in NP; one NP-complete problem in P would give \(\mathrm{P} = \mathrm{NP}\), and, by Lemma 20.2, a problem of NP to which a known NP-complete problem reduces is NP-complete in its turn.

Theorem 20.1 (Cook; Levin). SATISFIABILITY is NP-complete.

We refer to Cook 1971 and Levin 1973 for the proof, which writes, for a nondeterministic algorithm of polynomial time and an input \(x\), a formula of polynomial size whose variables describe the contents of the memory at each step and whose clauses force each step to follow from the one before it; the formula is satisfiable if and only if a sequence of choices leads to success. The book starts the chain from BOUNDED TILING instead, whose rows of tiles can encode the successive configurations of a computation in the same way (the tiles of Wang 1961), and reduces it to the other problems, as Karp 1972 did from SATISFIABILITY. Altogether, the functions of Reductions.h, and those of Problems.h that delegate to one another, realize the chain of Table 20.2, each in the time needed to write its output.

Table 20.2. The reductions realized in ADS/complexity (Montresor 2025, §18.5 and §18.7).

From To Where Function
BOUNDED TILING CLIQUE Theorem 18.2 dominoToClique()
BOUNDED TILING SATISFIABILITY Theorem 18.3 dominoToSat()
BOUNDED TILING 0-1 INTEGER PROGRAMMING Theorem 18.4 dominoToLp01()
CLIQUE INDEPENDENT SET Theorem 18.5 complement()
INDEPENDENT SET VERTEX COVER exercise 18.11 the complement of the set, \(k' = n - k\)
HAMILTONIAN CIRCUIT TRAVELING SALESMAN Theorem 18.6 hamiltonToTsp()
PARTITION MULTIPROCESSOR SCHEDULING, SUBSET SUM, KNAPSACK Theorems 18.7 to 18.9 halfSum()
HAMILTONIAN CIRCUIT DIRECTED HAMILTONIAN CIRCUIT exercise 18.12 both the orientations of each edge
DIRECTED HAMILTONIAN CIRCUIT DIRECTED HAMILTONIAN PATH exercise 18.13 cycleToPath()
DIRECTED HAMILTONIAN CIRCUIT HAMILTONIAN PATH exercise 18.14 cycleToChain()
DIRECTED HAMILTONIAN PATH LONGEST PATH exercise 18.15 \(k = n - 1\)
HAMILTONIAN PATH DEGREE-CONSTRAINED SPANNING TREE exercise 18.16 \(k = 2\)
3-DIMENSIONAL MATCHING EXACT COVER BY 3-SETS chapter 18 threeDimensionalMatching()

Each reduction rests on a correspondence between the certificates of the two problems, which we now state for the reductions from the tiling, the others being (somewhat) simpler. In all of them, the node, or the variable, of the tile \(h\) in the square \(( i , j )\) is \(u_{hij}\), at the place \(( h n + i ) n + j\) given by tileVar().

Lemma 20.3. In the graph of dominoToClique(), with \(m n^2\) nodes, the cliques of \(n^2\) nodes are the legal coverings when \(n \ge 2\); hence BOUNDED TILING \(\propto\) CLIQUE, in time \(\Theta( m^2 n^4 )\).

Proof. The graph joins \(u_{hij}\) to all the nodes of the squares not adjacent to \(( i , j )\), and to the nodes of the adjacent squares whose tile fits next to \(h\), and it leaves isolated the nodes of \(( 0 , 0 )\) but \(u_{000}\). Two nodes of one square are never joined, and therefore a clique of \(n^2\) nodes takes one tile per square, the tile \(d\) in \(( 0 , 0 )\); two of its tiles in adjacent squares are joined, i.e., they fit, and the clique is a legal covering. Conversely, the nodes of a legal covering are pairwise joined. Finally, the adjacency matrix has \(( m n^2 )^2\) entries. For \(n = 1\) an isolated node \(u_{h00}\), \(h \ne 0\), is a clique of one node too, but there both answers are YES (the tile \(d\) alone covers the board), and the reduction still satisfies (20.3). \(\square\)

The function dominoToSat() writes the same conditions as clauses on the variables \(u_{hij}\), true if the tile \(h\) is in \(( i , j )\). They are the unit clause \(u_{000}\), at least one tile and at most one tile in each square, and, for each pair of adjacent squares and each pair of tiles that do not fit there side by side, the clause that forbids both. The function dominoToLp01() writes them as linear constraints: \(x_{000} = 1\), one tile per square (each equation as two inequalities), and \(x_{hij}\) plus the tiles that do not fit next to it in a neighbouring square at most 1; the example of the text writes one inequality per pair, which is the same, since a square holds one tile (Algorithm 20.7).

Algorithm 20.7. The reductions of BOUNDED TILING to CLIQUE, to SATISFIABILITY and to 0-1 INTEGER PROGRAMMING (Theorems 18.2 to 18.4 of Montresor 2025).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{dominoToClique}( D , n )\quad \triangleright\ u_{hij} \text{: the tile } h \text{ on the square } ( i , j ) \cr 2 & \quad G \gets \text{the nodes } u_{hij} \text{, the square } ( 0 , 0 ) \text{ with } u_{000} \text{ only, and no edge} \cr 3 & \quad \textbf{foreach}\ \text{two nodes } u_{hij} , u_{gab} \text{ on distinct squares}\ \textbf{do} \cr 4 & \qquad \textbf{if}\ ( i , j ) , ( a , b ) \text{ are not adjacent, or the tiles } h , g \text{ match on their common side}\ \textbf{then}\ \text{join them} \cr 5 & \quad \textbf{return}\ ( G , n^2 )\quad \triangleright \ \text{a clique of } n^2 \text{ nodes is a tiling} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{dominoToSat}( D , n )\quad \triangleright \ u_{hij} \text{ true: the tile } h \text{ on } ( i , j ) \cr 2 & \quad F \gets ( u_{000} ) \cr 3 & \quad \text{add, for each square } ( i , j ) \text{, the clause } u_{0ij} \vee \cdots \vee u_{m-1,ij} \text{ and the clauses } \neg u_{hij} \vee \neg u_{gij} \text{, } h < g \cr 4 & \quad \text{add } \neg u_{hij} \vee \neg u_{g,i+1,j} \text{ when } D[ h ].\mathit{right} \ne D[ g ].\mathit{left} \text{, and } \neg u_{hij} \vee \neg u_{g,i,j+1} \text{ when } D[ h ].\mathit{up} \ne D[ g ].\mathit{down} \cr 5 & \quad \textbf{return}\ F \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{dominoToLp01}( D , n )\quad \triangleright\ x_{hij} = 1 \text{: the tile } h \text{ on } ( i , j ) \cr 2 & \quad \text{the rows } x_{000} = 1 \text{ and } \textstyle\sum_h x_{hij} = 1 \text{ for each square} \cr 3 & \quad \textbf{foreach}\ h \text{ and } ( i , j )\ \textbf{do} \ \text{the rows } x_{hij} + \textstyle\sum_g x_{g,i+1,j} \le 1 \cr & \qquad \text{and } x_{hij} + \textstyle\sum_g x_{g,i,j+1} \le 1 \text{,} \cr & \qquad \text{the sums over the tiles } g \text{ that do not fit on the right of } h \text{, and above } h \cr 4 & \quad \textbf{return}\ ( A , b )\quad \triangleright \ \text{each equation as two inequalities} \end{array} \]

The other reductions of the chain are simpler (Algorithm 20.8). The first, complement(), gives the complement graph, which has the edge \([ u , v ]\), \(u \ne v\), exactly when \(G\) does not, and hamiltonToTsp() gives the distance 1 on the edges of \(G\) and 2 elsewhere, with \(k = n\). The bound of halfSum() is half the sum of the numbers, or \(-1\) if the sum is odd, and the three numerical problems take the numbers themselves as the times of the programs on two processors with the deadline \(s / 2\), as the elements of SUBSET SUM, and as the profits and the volumes of KNAPSACK with the capacity and the target \(s / 2\). The function cycleToPath() splits the node 0 into a new node \(n\), which takes the edges out of 0, and the node 0, which keeps the edges into it. Finally, cycleToChain() makes each node \(v\) of the graph of cycleToPath() a chain \(v_{in} - v_{mid} - v_{out}\), each edge \(( u , v )\) an edge \([ u_{out} , v_{in} ]\), and adds a pendant node joined to \(n_{in}\) and one joined to \(0_{out}\), \(3 ( n + 1 ) + 2\) nodes in all. Both drop the loops of \(G\), as the problems of Problems.h ignore them.

Algorithm 20.8. The reductions of CLIQUE to INDEPENDENT SET, of HAMILTONIAN CIRCUIT to TRAVELING SALESMAN, of PARTITION to the numerical problems, and of the directed Hamiltonian circuit to the paths.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{complement}( G )\quad \triangleright \ \text{a clique of } G \text{ is an independent set of } C \cr 2 & \quad \textbf{return}\ C \text{ with } C[ u ][ v ] \text{ iff } u \ne v \text{ and not } G[ u ][ v ] \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{hamiltonToTsp}( G )\quad \triangleright \ \text{a circuit of cost } n \text{ iff } G \text{ is Hamiltonian} \cr 2 & \quad \textbf{return}\ D \text{ with } D[ i ][ i ] = 0 \text{, } D[ i ][ j ] = 1 \text{ on the edges of } G \text{ and } 2 \text{ elsewhere} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{halfSum}( A )\quad \triangleright \ \text{the target of the subset sum for a partition} \cr 2 & \quad s \gets \textstyle\sum_i A[ i ];\ \textbf{return}\ s / 2 \text{ if } s \text{ is even, else } -1 \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{cycleToPath}( G )\quad \triangleright \ \text{the node } 0 \text{ split into a start } 0 \text{ and an end } n \cr 2 & \quad H \gets \text{the nodes } 0 , \ldots , n \text{ and no edge} \cr 3 & \quad \textbf{foreach}\ ( u , v ) \in E \text{ with } u \ne v \ \textbf{do}\ \text{insert } ( n , v ) \text{ in } H \text{ if } u = 0 \text{, else } ( u , v ) \cr 4 & \quad \textbf{return}\ H \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{cycleToChain}( G )\quad \triangleright \ \text{each node } v \text{ of the path becomes the chain } v_{\mathrm{in}} , v_{\mathrm{mid}} , v_{\mathrm{out}} \cr 2 & \quad P \gets \mathrm{cycleToPath}( G );\ N \gets n + 1 \cr 3 & \quad \text{join } v_{\mathrm{in}} \text{ to } v_{\mathrm{mid}} \text{ and } v_{\mathrm{mid}} \text{ to } v_{\mathrm{out}} \text{ for each } v < N \text{, and } u_{\mathrm{out}} \text{ to } v_{\mathrm{in}} \text{ for each edge } ( u , v ) \text{ of } P \cr 4 & \quad \text{join a new node to } n_{\mathrm{in}} \text{ and another to } 0_{\mathrm{out}}\quad \triangleright \ \text{they fix the two ends} \cr 5 & \quad \textbf{return}\ \text{the graph of the } 3 N + 2 \text{ nodes} \end{array} \]

Lemma 20.4. Each function of Algorithm 20.8, and the complement of the set with \(k' = n - k\), satisfies (20.3) for the pair of problems of its row of Table 20.2, in time linear in the size of its output.

Proof. A set \(S\) is independent in \(G\) if and only if any two of its nodes are joined in the complement graph, i.e., \(S\) is a clique there. Also, \(S\) is independent if and only if \(V \setminus S\) covers the edges, since an edge left uncovered by \(V \setminus S\) has both its ends in \(S\); hence \(G\) has an independent set of \(k\) nodes if and only if it has a cover of \(n - k\) nodes. With the distances of hamiltonToTsp(), a tour has \(n\) edges of length at least 1, and its length is at most \(n\) if and only if all its edges are edges of \(G\), i.e., the tour is a Hamiltonian circuit of \(G\). If the sum \(s\) of the numbers is odd, no subset has the sum \(s / 2\), and the bound \(-1\) has no YES in any of the three problems, whose numbers are not negative. Otherwise, a subset of sum \(s / 2\) leaves the other half to the second processor, or out of the knapsack, and conversely a schedule within \(s / 2\) on two processors, a subset of sum \(s / 2\) or a knapsack of volume at most \(s / 2\) and profit at least \(s / 2\) splits the numbers into two halves of equal sum. For cycleToPath(), a Hamiltonian cycle of \(G\) read from the node 0, \(0 , v_1 , \ldots , v_{n-1} , 0\), becomes the path \(n , v_1 , \ldots , v_{n-1} , 0\), whose first edge is an edge out of 0 moved to \(n\), and conversely. For cycleToChain(), a directed Hamiltonian path \(n = w_0 , w_1 , \ldots , w_n = 0\) gives the path that starts at the pendant node of \(n_{in}\), runs along each chain \(w_{i,in} , w_{i,mid} , w_{i,out}\), passes from \(w_{i,out}\) to \(w_{i+1,in}\) by the edge of \(( w_i , w_{i+1} )\), and ends at the pendant node of \(0_{out}\). Conversely, in a Hamiltonian path of the unoriented graph the two pendant nodes, of degree 1, are the two ends, and each node \(v_{mid}\), of degree 2 and not an end, is passed between \(v_{in}\) and \(v_{out}\). Hence the path, from the pendant node of \(n_{in}\), runs along the chain of \(n\) from \(n_{in}\) to \(n_{out}\); from a node \(u_{out}\) it can only go to a node \(v_{in}\) with \(( u , v )\) an edge of the graph of cycleToPath() (or to the final pendant node, if \(u = 0\)), and from \(v_{in}\) along the chain of \(v\) to \(v_{out}\). By induction the chains are crossed in the order of a directed Hamiltonian path from \(n\) to 0. Each function writes each entry of its output a constant number of times. \(\square\)

The same tool proves lower bounds within P. Sorting reduces to the convex hull (sortToHull(), Algorithm 20.9), which maps each number \(a_i\) to the point \(( a_i , a_i^2 )\) of a parabola (Montresor 2025, §18.5). Note that the squares of the numbers must fit in a long, which is a precondition.

Algorithm 20.9. The reduction of sorting to the convex hull.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{sortToHull}( a )\quad \triangleright \ \text{the points on the parabola } y = x^2 \text{ are all on the hull} \cr 2 & \quad \textbf{return}\ ( ( a_i , a_i^2 ) : i = 1 , \ldots , n ) \end{array} \]

Lemma 20.5. The distinct points \(( a_i , a_i^2 )\) are all vertices of their convex hull, and its boundary in counterclockwise order from the leftmost vertex lists them by increasing \(a_i\). Hence an algorithm that computes the convex hull of \(n\) points with \(o( n \log n )\) comparisons would sort \(n\) numbers with \(o( n \log n )\) comparisons, and the convex hull costs \(\Omega( n \log n )\) comparisons in the worst case.

Proof. For a point \(( b , b^2 )\) of the set, the line \(y = 2 b x - b^2\) leaves all the other points \(( a , a^2 )\) strictly above it, since \(a^2 - 2 b a + b^2 = ( a - b )^2 > 0\); hence \(( b , b^2 )\) is the only point of the set that minimizes \(y - 2 b x\), i.e., a vertex of the hull. The points below the segment that joins the leftmost and the rightmost point are the lower chain of the hull, which a counterclockwise traversal visits from the leftmost to the rightmost vertex by increasing abscissa, and no point lies above that segment, by the convexity of \(x^2\); thus the traversal from the leftmost vertex is the sorted order. Equal numbers give the same point, and the order of the distinct values, with their multiplicities counted in \(O( n )\) by a scan, is the sorted sequence. The map and the reading of the hull cost \(O( n )\), and the lower bound \(\Omega( n \log n )\) of the sorting by comparisons applies. \(\square\)

20.5 Polynomial cases

The square tiling is NP-complete, while the tiling of a strip \(1 \times n\) is in P (Montresor 2025, §18.5). A strip is a walk of \(n - 1\) edges from \(d\) in the graph \(H\) whose nodes are the \(m\) tiles and whose edges \(( d_u , d_v )\) join a tile to those that fit on its right.

Lemma 20.6 (the linear tiling). A strip of \(n\) tiles from \(d\) exists if and only if

\[ \text{a cycle of } H \text{ is reachable from } d \quad \text{or} \quad L( d ) \ge n - 1 , \tag{20.4} \]

\(L( d )\) being the number of the edges of the longest path from \(d\). The function linearTiling() decides (20.4) in \(O( m^2 )\) time, whatever \(n\) is.

Proof. A walk may go round a reachable cycle as many times as it needs, and so has any length; without a reachable cycle, each walk from \(d\) is a path, and its length is at most \(L( d )\). One visit in depth of \(H\) from \(d\) finds a reachable cycle as a back edge, i.e., an edge to a node still open, and computes \(L\) in the postvisit, since without cycles the longest path from \(u\) is one edge plus the longest from a successor. The visit examines the \(m^2\) pairs of tiles of the implicit matrix of \(H\) once each. \(\square\)

Note that \(n\) enters the input with \(\log n\) bits, and an enumeration of the strips would take time exponential in it; the visit, instead, does not depend on \(n\) at all (Algorithm 20.10).

Algorithm 20.10. The linear tiling by a visit in depth of the graph of the tiles.

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{visit}( u )\quad \triangleright \ \text{the graph of the tiles, } u \to v \text{ if } v \text{ fits right of } u \cr 2 & \quad \mathit{state}[ u ] \gets \text{open} \cr 3 & \quad \textbf{foreach}\ v \text{ with } D[ v ].\mathit{left} = D[ u ].\mathit{right}\ \textbf{do} \cr 4 & \qquad \textbf{if}\ \mathit{state}[ v ] = \text{new}\ \textbf{then} \ \mathrm{visit}( v )\ \textbf{else if}\ \mathit{state}[ v ] = \text{open}\ \textbf{then}\ \mathit{cycle} \gets \textbf{true} \cr 5 & \qquad L[ u ] \gets \max\{ L[ u ] , L[ v ] + 1 \}\quad \triangleright\ \text{the longest row from } u \cr 6 & \quad \mathit{state}[ u ] \gets \text{done} \cr 7 & \textbf{function}\ \mathrm{linearTiling}( D , n )\quad \triangleright\ \text{a row of } n \text{ tiles from the tile } 0 \cr 8 & \quad \textbf{if}\ n < 1\ \textbf{or}\ m = 0 \ \textbf{then return false} \cr 9 & \quad \mathrm{visit}( 0 );\ \textbf{return}\ \mathit{cycle} \text{ or } n - 1 \le L[ 0 ]\quad \triangleright \ \text{a cycle gives rows of any length} \end{array} \]

In its conclusion, Montresor 2025 pairs several NP-complete problems with a polynomial one that differs from it in a detail, and EasyCases.h realizes the polynomial halves that the other areas do not (Table 20.3).

Table 20.3. The polynomial halves of the pairs of table 19.1 of the book, and where the library realizes them.

NP-complete Polynomial Where
SATISFIABILITY, three literals per clause two literals per clause twoSat()
3-COLORABILITY 2-COLORABILITY twoColoring()
3-DIMENSIONAL MATCHING 2-DIMENSIONAL MATCHING bipartiteMatching()
CLIQUE CLIQUE on an interval graph intervalClique()
BOUNDED TILING the linear tiling linearTiling() of Domino.h
HAMILTONIAN CIRCUIT the Eulerian cycle eulerianCycle() of EulerianCycle.h
KNAPSACK the fractional knapsack fractionalKnapsack() (§13.11)
DEGREE-CONSTRAINED SPANNING TREE the minimum spanning tree kruskal() of MinimumSpanningTree.h
LONGEST PATH the shortest path shortestPaths() of ShortestPaths.h

Theorem 20.2 (Aspvall, Plass and Tarjan). A formula of clauses of at most two literals is satisfiable if and only if no variable \(v\) lies in the strongly connected component of \(\neg v\) in the graph of the implications, which has the edges \(( \neg a , b )\) and \(( \neg b , a )\) for each clause \(a \vee b\); the assignment that makes \(v\) true when the component of \(v\) comes after that of \(\neg v\) in a topological order of the components satisfies the formula.

Proof. A path of implications from \(v\) to \(\neg v\) and one back would force \(v\) to be both true and false. Conversely, write \(\kappa( a )\) for the place of the component of the literal \(a\) in the topological order, so that an edge \(( a , b )\) gives \(\kappa( a ) \le \kappa( b )\). Suppose that the assignment of the statement sets a literal \(a\) true and a successor \(b\) of it false, i.e., \(\kappa( \neg a ) < \kappa( a )\) and \(\kappa( b ) < \kappa( \neg b )\). Since the graph is symmetric under negation (it has \(( \neg b , \neg a )\) whenever it has \(( a , b )\)), one has \(\kappa( \neg a ) < \kappa( a ) \le \kappa( b ) < \kappa( \neg b ) \le \kappa( \neg a )\), which is impossible. A clause \(a \vee b\) made false would give such a pair, the edge \(( \neg a , b )\) from a true literal to a false one (Aspvall, Plass and Tarjan 1979). \(\square\)

The function twoSat() takes a clause of one literal \(a\) as \(a \vee a\), builds the graph of the \(2 n\) literals (the literal \(\pm( v + 1 )\) at the node \(2 v\) or \(2 v + 1\), by literalNode()) with each implication once. Then it ranks each strongly connected component by its first node in the order of decreasing finish time of the visit in depth of topsort(), which is a topological order of the components by Lemma 20.7 below (Algorithm 20.11). All this takes \(O( n + m )\) time for \(m\) clauses (up to the logarithmic factor of the set that removes the repeated implications).

Algorithm 20.11. The polynomial halves: 2-SATISFIABILITY, 2-COLORABILITY, the bipartite matching, and the cliques of an interval graph.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{twoSat}( F , n ) \cr 2 & \quad G \gets \text{a graph of the } 2 n \text{ literals and no edge} \cr 3 & \quad \textbf{foreach}\ a \vee b \in F\ \textbf{do}\ \text{insert } ( \neg a , b ) \text{ and } ( \neg b , a ) \text{ in } G \cr 4 & \quad C \gets \mathrm{scc}( G );\ r \gets \text{the rank of each component}\ \text{in the order of } \mathrm{topsort}( G ) \cr 5 & \quad \textbf{for}\ v \gets 0\ \textbf{to}\ n - 1\ \textbf{do} \cr 6 & \qquad \textbf{if}\ C[ v ] = C[ \neg v ]\ \textbf{then return nil} \cr 7 & \qquad x[ v ] \gets r[ C[ v ] ] > r[ C[ \neg v ] ] \cr 8 & \quad \textbf{return}\ x \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{twoColoring}( G )\quad \triangleright \ \text{a visit in breadth of each component} \cr 2 & \quad c[ v ] \gets \textbf{nil} \text{ for every node } v \cr 3 & \quad \textbf{foreach}\ r \text{ with } c[ r ] = \textbf{nil} \ \textbf{do} \cr 4 & \qquad c[ r ] \gets 0;\ Q \gets ( r ) \cr 5 & \qquad \textbf{while}\ Q \ne \emptyset\ \textbf{do} \cr 6 & \qquad\quad u \gets \mathrm{dequeue}( Q ) \cr 7 & \qquad\quad \textbf{foreach}\ v \ne u \text{ with } G[ u ][ v ] \ \textbf{do}\quad \triangleright \ \text{the other color, or an odd cycle} \cr 8 & \qquad\qquad \textbf{if}\ c[ v ] = \textbf{nil}\ \textbf{then}\ c[ v ] \gets 1 - c[ u ];\ \mathrm{enqueue}( Q , v )\ \textbf{else if}\ c[ v ] = c[ u ]\ \textbf{then return nil} \cr 9 & \quad \textbf{return}\ c \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{bipartiteMatching}( p , q , E )\quad \triangleright\ \text{a maximum flow of unit capacities} \cr 2 & \quad N \gets \text{a network on } 0 , \ldots , p + q + 1 \text{, with the source } s = p + q \text{ and the sink } t = p + q + 1 \cr 3 & \quad \text{add } ( s , i ) \text{, } ( i , p + j ) \text{ and } ( p + j , t ) \text{ of capacity } 1 \text{ for each } i < p \text{, } ( i , j ) \in E \text{, } j < q \cr 4 & \quad N.\mathrm{maxFlow}( s , t ) \cr 5 & \quad \textbf{return}\ \text{the pairs } ( i , j ) \in E \text{ whose edge carries flow} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{intervalGraph}( I ) \cr 2 & \quad \textbf{return}\ \text{the graph with } G[ u ][ v ] \text{ iff } u \ne v \text{ and } \max\{ a_u , a_v \} < \min\{ b_u , b_v \}\quad \triangleright\ \text{they meet} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{intervalClique}( I )\quad \triangleright \ \text{the most intervals over one point} \cr 2 & \quad P \gets \text{the ends of } I \text{, a left end as } ( a , +1 ) \text{, a right end as } ( b , -1 ) \cr 3 & \quad \text{sort } P \text{ by abscissa, a right end first on a tie}\quad \triangleright \ [ a , b ) \text{ is open on the right} \cr 4 & \quad \textbf{return}\ \text{the largest prefix sum of the signs of } P \text{, or } 0 \end{array} \]

Similarly, a graph is 2-colorable if and only if it has no odd cycle, which the visit in breadth of twoColoring() finds as an edge between two nodes of the same color, in \(O( n^2 )\) on the adjacency matrix (the diagonal ignored, as by coloring()). A bipartite matching is a maximum flow with unit capacities from a source to the left nodes, along the edges, to a sink (bipartiteMatching(), by the reduction of section 15.2 of the book). On intervals of the line, finally, a set that meets pairwise has a common point, and the largest clique of the graph of the intervals \([ a , b )\) built by intervalGraph() is counted by a sweep of the sorted ends in \(O( n \log n )\) (intervalClique(), the right ends before the left ones at equal abscissa).

Lemma 20.7. (i) If the components \(C\) and \(C'\) of a graph are joined by an edge from \(C\) to \(C'\), the node of \(C\) that finishes last in a visit in depth finishes after each node of \(C'\); hence ranking the components by their first node in the order of decreasing finish time is a topological order of the components. (ii) twoColoring() returns a coloring with no edge between two nodes of the same color if the graph has no odd cycle, and nil otherwise. (iii) intervalClique() returns the largest number of intervals through one point, which is the size of the largest clique of the graph of intervalGraph(); an empty interval meets no other one.

Proof. (i) Let \(x\) be the first node of \(C \cup C'\) that the visit discovers. If \(x \in C\), all the nodes of \(C \cup C'\) are still new and reachable from \(x\), and hence they finish before \(x\). If \(x \in C'\), no node of \(C\) is reachable from \(C'\) (otherwise \(C\) and \(C'\) would be one component), and all the nodes of \(C'\) finish before the visit discovers a node of \(C\). In both cases a node of \(C\) finishes after all the nodes of \(C'\), and so the first node of \(C\) in the decreasing order precedes those of \(C'\). (ii) In the visit in breadth from a root \(r\), the color of a node is the parity of its distance from \(r\), and the distances of two adjacent nodes differ by at most 1. Hence an edge between two nodes of the same color joins two nodes at the same distance \(d\), and the two paths from \(r\) in the tree of the visit, with that edge, form a closed walk of \(2 d + 1\) edges, which contains an odd cycle; a graph with an odd cycle has no coloring with 2 colors, since the colors would alternate along the cycle. If the visit returns, each edge has been examined from both its ends with different colors. (iii) Two intervals \([ a , b )\) and \([ a' , b' )\) meet if and only if \(a < b'\) and \(a' < b\). For a set of intervals that meet pairwise, the largest left end \(a^*\) is below each right end, and hence belongs to all of them (the property of Helly in one dimension); thus the largest clique is the largest number of intervals through one point, and conversely the intervals through one point meet pairwise. In the sweep, after the events of the abscissae up to \(x\), the right ends at \(x\) first, \(c\) is the number of the intervals \([ a , b )\) with \(a \le x < b\), i.e., through \(x\); the values of \(c\) between two such moments are not larger than one of them, and an empty interval \([ a , a )\) adds \(-1\) before \(+1\) at \(a\). \(\square\)

20.6 Pseudopolynomial algorithms

We now turn to the strategies for the problems that are NP-hard. A problem of optimization requires, for an instance \(x\), a feasible solution of least cost (or of largest value) among the set \(F( x )\) of the feasible ones; \(x^*\) is an optimal solution and \(\mathit{OPT} = c( x^* )\) its cost. When the decision version is NP-complete, no algorithm is known that finds \(x^*\) in polynomial time on each instance, and each strategy gives up something. An algorithm is pseudopolynomial if its time is bounded by a polynomial in the size \(d\) of the instance and in its largest integer \(\#\) (Montresor 2025, §19.1); since \(\#\) may be exponential in \(d\), such an algorithm is polynomial only on the instances whose numbers are "small". For SUBSET SUM, with \(M[ i ][ j ]\) true if some of the first \(i\) elements sum to \(j\),

\[ M[ i ][ j ] = M[ i - 1 ][ j ] \ \text{or} \ ( j \ge A_i \ \text{and} \ M[ i - 1 ][ j - A_i ] ) , \tag{20.5} \]

since a subset of the first \(i\) elements either avoids the \(i\)-th or takes it once. The function subsetSumDP() of Pseudopolynomial.h fills (20.5) in \(O( n k )\) time with one row of \(k + 1\) bits, written from the right, so that \(M[ j - A_i ]\) is still the value of the row before (Algorithm 20.12). The row is a vector of Bits, which may be std::vector< bool > (the default), boost::dynamic_bitset or the BitVector of the library, with the same cells written. If a pointer rows is given, the function appends there the row after each element. The function subsetSumSet() keeps all the rows, and reads a subset backwards (an element is needed when the row above does not have the sum), in \(O( n k )\) time and space; partitionDP() (exercise 19.1) is the same with half the sum.

Algorithm 20.12. SUBSET SUM and PARTITION by dynamic programming (Montresor 2025, §19.1 and exercise 19.1).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{subsetSumDP}( A , k )\quad \triangleright \ M[ j ] \text{: some subset of the items seen sums to } j \cr 2 & \quad \textbf{if}\ k < 0\ \textbf{then return false} \cr 3 & \quad M \gets ( \textbf{true} , \textbf{false} , \ldots , \textbf{false} ) \text{, of } k + 1 \text{ entries} \cr 4 & \quad \textbf{foreach}\ a \in A\ \textbf{do}\ M[ j ] \gets M[ j ] \text{ or } M[ j - a ] \text{ for } j = k , k - 1 , \ldots , a\quad \triangleright\ \text{downwards: } a \text{ once} \cr 5 & \quad \textbf{return}\ M[ k ] \end{array} \]

Lemma 20.8. After the \(i\)-th element \(a = A_i\) of line 4, \(M[ j ] = M[ i ][ j ]\) of (20.5) for \(0 \le j \le k\); hence subsetSumDP() decides SUBSET SUM in \(O( n k )\) time and \(k + 1\) bits.

Proof. Before the first element, \(M[ j ]\) is true only for \(j = 0\), the sum of the empty subset. Let the claim hold after the element \(i - 1\). In the pass of line 4 for \(a = A_i\), the entry \(j\) is written after the entries above it and before those below it; hence, when \(M[ j ]\) is written, \(M[ j - a ]\), with \(j - a \le j\), still holds \(M[ i - 1 ][ j - a ]\) (for \(a = 0\) the two are the same entry, and the or leaves it as it was). The entry \(j\) thus becomes \(M[ i - 1 ][ j ]\) or \(M[ i - 1 ][ j - a ]\), which is (20.5), while the entries \(j < a\), not written, keep \(M[ i - 1 ][ j ] = M[ i ][ j ]\). Finally, (20.5) is correct, since a subset of the first \(i\) elements either avoids the \(i\)-th or takes it once. \(\square\)

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{subsetSumSet}( A , k )\quad \triangleright\ M[ i ][ j ] \text{ for the first } i \text{ items} \cr 2 & \quad \textbf{if}\ k < 0\ \textbf{then return nil} \cr 3 & \quad M[ 0 ][ j ] \gets ( j = 0 ) \text{ for every } j \cr 4 & \quad M[ i + 1 ][ j ] \gets M[ i ][ j ] \text{ or } ( A[ i ] \le j \text{ and } M[ i ][ j - A[ i ] ] ) \text{, for } i < n \text{ and } j \le k \cr 5 & \quad \textbf{if}\ \textbf{not}\ M[ n ][ k ] \ \textbf{then return nil} \cr 6 & \quad S \gets \emptyset;\ j \gets k \cr 7 & \quad \textbf{for}\ i \gets n\ \textbf{downto}\ 1\ \textbf{do}\quad \triangleright\ \text{the item } i - 1 \text{ is needed iff } j \text{ was not reachable without it} \cr 8 & \qquad \textbf{if}\ \textbf{not}\ M[ i - 1 ][ j ]\ \textbf{then}\ S \gets S \cup \{ i - 1 \};\ j \gets j - A[ i - 1 ] \cr 9 & \quad \textbf{return}\ S \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{partitionDP}( A )\quad \triangleright \ \text{two halves of equal sum} \cr 2 & \quad s \gets \textstyle\sum_i A[ i ] \cr 3 & \quad \textbf{return}\ \textbf{nil} \text{ if } s \text{ is odd, else } \mathrm{subsetSumSet}( A , s / 2 ) \end{array} \]

With more parts, the same idea gives the other dynamic programmings of the header (Algorithm 20.13). In bottino() (exercise 19.5), three thieves share jewels of prices \(P[ i ]\) so that each takes a third of the value \(m\). There \(S[ i ][ j ][ h ]\) records whether the first \(i\) jewels give \(j\) to the first thief and \(h\) to the second, the third taking what is left; since the prices are not negative \(j\) and \(h\) range in \([ 0 , m / 3 ]\), i.e., \(O( n m^2 )\) entries. In schedulingDP() (exercise 19.2), the vectors of the loads of the \(m\) processors reachable with the first \(i\) programs, each load at most \(d\), are at most \(( d + 1 )^m\) after each program, and the time is \(O( n ( d + 1 )^m )\), pseudopolynomial for \(m\) fixed.

Algorithm 20.13. The loot of the three thieves, and MULTIPROCESSOR SCHEDULING by the vectors of the loads.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{bottino}( P )\quad \triangleright\ S[ i ][ j ][ h ] \text{: the first } i \text{ items give } j \text{ to one thief and } h \text{ to another} \cr 2 & \quad m \gets \textstyle\sum_i P[ i ];\ \textbf{if}\ 3 \nmid m \ \textbf{then return nil} \cr 3 & \quad S[ 0 ][ j ][ h ] \gets ( j = h = 0 ) \cr 4 & \quad \textbf{foreach}\ i \in [ 0 , n ) \text{ and } j , h \in [ 0 , m / 3 ]\ \textbf{do}\quad \triangleright\ \text{the item } i \text{ to the third thief, the first or the second} \cr 5 & \qquad S[ i + 1 ][ j ][ h ] \gets S[ i ][ j ][ h ] \text{ or } S[ i ][ j - P[ i ] ][ h ] \text{ or } S[ i ][ j ][ h - P[ i ] ] \cr 6 & \quad \textbf{return}\ \textbf{nil} \text{ if not } S[ n ][ m / 3 ][ m / 3 ] \text{, else the thief of each item, read back from it} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{schedulingDP}( t , m , d )\quad \triangleright\ L_i \text{ the loads of the } m \text{ processors after } i \text{ jobs} \cr 2 & \quad \textbf{if}\ d < 0\ \textbf{then return nil} \cr 3 & \quad L_0 \gets \{ ( 0 , \ldots , 0 ) \} \cr 4 & \quad L_{i+1} \gets \{ x + t_i e_q : x \in L_i \text{, } x_q + t_i \le d \} \text{ for } i = 0 , \ldots , n - 1\quad \triangleright \ \text{a set: no copies} \cr 5 & \quad \textbf{return}\ \textbf{nil} \text{ if } L_n = \emptyset \text{, else the processor of each job, read back from a vector of } L_n \end{array} \]

A problem is strongly NP-complete if it stays NP-complete on the instances with \(\#\) bounded by a polynomial in \(d\) (CLIQUE, whose numbers are bounded by \(n\), TRAVELING SALESMAN, 3-PARTITION), and weakly otherwise (SUBSET SUM, PARTITION, KNAPSACK); cf. Garey and Johnson 1978.

Theorem 20.3. A strongly NP-complete problem has no pseudopolynomial algorithm unless \(\mathrm{P} = \mathrm{NP}\).

Proof. On the instances with \(\# \le q( d )\), \(q\) a polynomial, the time of a pseudopolynomial algorithm is a polynomial in \(d\) and \(q( d )\), i.e., in \(d\); such an algorithm would solve in polynomial time a restriction that is NP-complete. \(\square\)

When a program may be interrupted and resumed on another processor, the scheduling becomes easy. No schedule is shorter than

\[ d = \max\Bigl\{ \max_i t_i , \ \sum_i t_i / m \Bigr\} , \tag{20.6} \]

since each program runs for its time and the \(m\) processors do at most \(m d\) work, and the rule of McNaughton 1959 (mcNaughton(), exercise 19.3) reaches (20.6) by filling the processors one after the other up to \(d\), in \(O( n + m )\) time (Algorithm 20.14).

Lemma 20.9. The schedule of mcNaughton() runs each program for its time within \([ 0 , d ]\), and never on two processors at once; hence it is optimal, and realTimeScheduling() succeeds if and only if \(C_i \le T_i\) for each \(i\) and \(\sum_i C_i / T_i \le m\).

Proof. A program split between the processors \(q\) and \(q + 1\) runs on \(q\) from some time \(s\) to \(d\), and on \(q + 1\) from 0 to \(t_i - ( d - s )\); since \(t_i \le d\), one has \(t_i - ( d - s ) \le s\), and the two pieces do not overlap in time. Also, the total work \(\sum_i t_i \le m d\) fits in the \(m\) processors, and the loop of line 5 never runs out of processors with work left. The length \(d\) is the lower bound (20.6), and hence optimal. For realTimeScheduling(), \(d \le 1\) if and only if \(\max_i C_i / T_i \le 1\) and \(\sum_i C_i / T_i \le m\). When \(d > 1\), no schedule of a period exists, again by (20.6). \(\square\)

With \(t_i = C_i / T_i\) and \(d = 1\), the same rule schedules a period of the periodic tasks of REAL-TIME SCHEDULING without a priority rule (realTimeScheduling(), exercise 19.4), the task \(i\) running for the fraction \(C_i / T_i\) of each period, which succeeds if and only if \(C_i \le T_i\) for each \(i\) and \(\sum_i C_i / T_i \le m\). Schedules are lists of Pieces, each the program and the interval \([ \mathit{start} , \mathit{end} )\) in which it runs, and the contracts check them as a postcondition.

Algorithm 20.14. The rule of McNaughton, and REAL-TIME SCHEDULING (Montresor 2025, exercises 19.3 and 19.4).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{mcNaughton}( t , m )\quad \triangleright \ d \text{ the optimum, a lower bound met} \cr 2 & \quad d \gets \max\{ \max_i t_i , \textstyle\sum_i t_i / m \};\ q \gets 0;\ \mathit{now} \gets 0\quad \triangleright \ \text{the processor and the time filled} \cr 3 & \quad \textbf{foreach}\ \text{job } i \text{, in order}\ \textbf{do} \cr 4 & \qquad r \gets t_i \cr 5 & \qquad \textbf{while}\ r > 0 \text{ and } q < m\ \textbf{do}\quad \triangleright\ \text{a job split ends on } q \text{ and restarts on } q + 1 \cr 6 & \qquad\quad s \gets \min\{ r , d - \mathit{now} \};\ \text{give } i \text{ the time } [ \mathit{now} , \mathit{now} + s ) \text{ of } q \cr 7 & \qquad\quad r \gets r - s;\ \mathit{now} \gets \mathit{now} + s; \ \textbf{if}\ \mathit{now} = d\ \textbf{then}\ ( q , \mathit{now} ) \gets ( q + 1 , 0 ) \cr 8 & \quad \textbf{return}\ ( d , \text{the pieces} ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{realTimeScheduling}( C , T , m )\quad \triangleright\ \text{the utilizations as the lengths of the jobs} \cr 2 & \quad ( d , P ) \gets \mathrm{mcNaughton}( ( C_i / T_i : i = 1 , \ldots , n ) , m ) \cr 3 & \quad \textbf{return}\ P \text{ if } d \le 1 \text{, else } \textbf{nil} \end{array} \]

20.7 Approximation algorithms

An algorithm is an approximation with relative error \(e\) if it gives a feasible \(x'\) with

\[ \frac{\lvert c( x' ) - \mathit{OPT} \rvert}{\mathit{OPT}} \le e \tag{20.7} \]

on each instance, and an approximation scheme if it takes \(\epsilon > 0\) in input and satisfies (20.7) with \(e = \epsilon\) in a time polynomial in \(d\) for each fixed \(\epsilon\) (fully polynomial if also in \(1 / \epsilon\)) (Montresor 2025, §19.2). All the guarantees of Approximation.h rest on a lower bound of \(\mathit{OPT}\) that the algorithm can compare with its own cost (Table 20.4).

Table 20.4. The approximations of Approximation.h (Montresor 2025, §19.2 and exercises 19.6 and 19.8); \(N\) and \(N^*\) are the boxes used and the fewest possible.

Problem Function Guarantee Time
BIN PACKING firstFit() \(N < 2 N^*\) \(O( n^2 )\)
TRAVELING SALESMAN, triangular deltaTsp() \(c( x' ) \le 2 \, \mathit{OPT}\) \(O( n^2 \log n )\)
SUBSET SUM apSubsetSum() \(e < 1 / ( h + 1 )\) \(O( h n^{h+1} )\)
VERTEX COVER vertexCoverApprox() \(\lvert S \rvert \le 2 \, \mathit{OPT}\) \(O( n^2 )\)
KNAPSACK knapsackApprox() \(c( x' ) \ge ( 1 - \epsilon ) \mathit{OPT}\) \(O( n^3 / \epsilon )\)

Bin packing. The function firstFit() puts each object of volume in \([ 0 , k ]\) in the first box with room for it, the objects in the order given (ff) or by decreasing volume (ffd), and opens a new box when none has room (Algorithm 20.15).

Algorithm 20.15. The first fit, and its decreasing variant, for BIN PACKING.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{firstFit}( A , k , \mathit{decreasing} )\quad \triangleright\ F[ b ] \text{ the room left in the box } b \cr 2 & \quad F \gets () \cr 3 & \quad \textbf{foreach}\ i \in [ 0 , n ) \text{, by decreasing } A[ i ] \text{ if } \mathit{decreasing} \text{, else by index}\ \textbf{do} \cr 4 & \qquad b \gets \text{the first box with } A[ i ] \le F[ b ] \text{, or a new last box with } F[ b ] = k \cr 5 & \qquad \mathit{box}[ i ] \gets b;\ F[ b ] \gets F[ b ] - A[ i ] \cr 6 & \quad \textbf{return}\ \mathit{box} \end{array} \]

Lemma 20.10. If some object has a positive volume, the first fit uses \(N < 2 N^*\) boxes.

Proof. No two boxes have contents that sum to at most \(k\), since the objects of the later one would have fitted in the earlier one. If \(N \ge 2\), summing the contents of the \(N\) pairs of consecutive boxes (the last with the first) counts each box twice, and twice the total volume \(V\) exceeds \(N k\); since \(N^* \ge V / k\), one has \(N < 2 V / k \le 2 N^*\). If \(N = 1\), then \(N^* = 1\). \(\square\)

In practice, the decreasing order of ffd usually helps, and it improves the constant, to \(11 / 9\) asymptotically (Johnson et al. 1974). Since a box is found by a scan, the time is \(O( n N )\), i.e., \(O( n^2 )\) in the worst case.

The triangular salesman. The function deltaTsp() builds a minimum spanning tree \(T\) of the complete graph of the symmetric distances (by kruskal() on the \(n ( n - 1 ) / 2\) edges, whence the time \(O( n^2 \log n )\)), and returns the cities in the preorder of \(T\) from 0, the children by increasing name (Algorithm 20.16; Rosenkrantz, Stearns and Lewis 1977). The function tourCost() gives the cost of a circuit.

Lemma 20.11. If the distances satisfy the triangle inequality, the circuit of deltaTsp() costs at most \(2 \, \mathit{OPT}\).

Proof. The tree \(T\) weighs no more than any circuit, which is a spanning path plus an edge of nonnegative cost, and the walk that goes twice along each edge of \(T\) costs \(2 w( T ) \le 2 \, \mathit{OPT}\). Then the preorder visits the cities in the order of their first visit by the walk, and each shortcut over the cities already visited costs no more than the stretch of the walk that it replaces, by the triangle inequality. \(\square\)

The bound is reached, up to a vanishing term, by the two concentric polygons of figure 19.3 of the book. We remark that the triangle inequality is checked by an audit in \(O( n^3 )\), with a relative tolerance for the floating point. Without it there is no constant at all, as follows.

Theorem 20.4. For no constant \(s \ge 1\) does TRAVELING SALESMAN have a polynomial algorithm with \(c( x' ) \le s \, \mathit{OPT}\), unless \(\mathrm{P} = \mathrm{NP}\).

Proof. With the distances of tspGap(), 1 on the edges of \(G\) and \(s n\) elsewhere, a Hamiltonian circuit of \(G\) is a tour of cost \(n\), while any other tour costs more than \(s n\); an algorithm within \(s\) would therefore return a tour of cost at most \(s n\) if and only if \(G\) has a Hamiltonian circuit, and decide HAMILTONIAN CIRCUIT in polynomial time. \(\square\)

Algorithm 20.16. The salesman with the triangle inequality, and the distances of Theorem 19.2 of the book.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{deltaTsp}( D )\quad \triangleright \ \text{at most twice the optimum under the triangle inequality} \cr 2 & \quad T \gets \text{the minimum spanning tree by } \mathrm{kruskal} \text{ of the complete graph weighted by } D \cr 3 & \quad \textbf{return}\ \text{the previsit of } T \text{ from } 0 \text{, the children by increasing name}\quad \triangleright \ \text{shortcuts of the walk} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{tspGap}( G , s )\quad \triangleright \ \text{a circuit of cost } n \text{ iff } G \text{ is Hamiltonian} \cr 2 & \quad \textbf{return}\ D \text{ with } D[ u ][ u ] = 0 \text{, and } D[ u ][ v ] = 1 \text{ on the edges of } G \text{, } s n \text{ elsewhere} \end{array} \]

Subset sum. For the optimization version of SUBSET SUM (the largest sum at most \(k\)), apSubsetSum() tries each set of at most \(h\) elements, in the order of the text (by size, then lexicographically on the elements in decreasing order), and completes it greedily on the elements in decreasing order (Algorithm 20.17).

Lemma 20.12. Let \(z^* \le k\) be the optimum. The sum \(z\) found by apSubsetSum() is either \(z^*\), or

\[ z > z^* \Bigl( 1 - \frac{1}{h + 1} \Bigr) ; \tag{20.8} \]

the time is \(O( h n^{h+1} )\).

Proof. Let \(S^*\) be optimal. If \(\lvert S^* \rvert \le h\), the algorithm tries \(S^*\) itself. Otherwise it tries the \(h\) largest elements of \(S^*\), and the greedy completion either takes all of \(S^*\) or leaves out an element \(a\) of \(S^*\), not larger than those \(h\), with \(z + a > k \ge z^*\). Since \(( h + 1 ) a \le z^*\), one has \(z > z^* - a \ge z^* ( 1 - 1 / ( h + 1 ) )\). As for the time, the \(O( n^h )\) sets of at most \(h\) elements are each built in \(O( h )\) and completed in \(O( n )\). \(\square\)

Algorithm 20.17. The approximation of SUBSET SUM, the cover by the ends of a matching, and the approximation scheme of KNAPSACK.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{apSubsetSum}( A , k , h )\quad \triangleright\ \text{each seed of } h \text{ items at most, then a greedy completion} \cr 2 & \quad ( \mathit{max} , \mathit{maxSol} ) \gets ( 0 , \emptyset ) \cr 3 & \quad \textbf{foreach}\ S \subseteq \{ 1 , \ldots , n \} \text{ with } |S| \le h \text{ and } z = \textstyle\sum_{j \in S} A[ j ] \le k\ \textbf{do} \cr 4 & \qquad \textbf{foreach}\ j \notin S \text{, from } 1 \text{ to } n \ \textbf{do}\ \textbf{if}\ z + A[ j ] \le k\ \textbf{then}\ S \gets S \cup \{ j \};\ z \gets z + A[ j ] \cr 5 & \qquad \textbf{if}\ \mathit{max} \le z\ \textbf{then}\ ( \mathit{max} , \mathit{maxSol} ) \gets ( z , S ) \cr 6 & \quad \textbf{return}\ ( \mathit{max} , \mathit{maxSol} ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{vertexCoverApprox}( G )\quad \triangleright \ \text{the ends of a maximal matching: twice the optimum} \cr 2 & \quad S \gets \emptyset \cr 3 & \quad \textbf{foreach}\ [ u , v ] \in E \text{, } u < v \text{, in lexicographic order, with } u , v \notin S\ \textbf{do}\ S \gets S \cup \{ u , v \} \cr 4 & \quad \textbf{return}\ S \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{knapsackApprox}( p , v , C , \epsilon ) \cr 2 & \quad I \gets \text{the objects that fit alone};\ \textbf{if}\ I = \emptyset\ \textbf{then return}\ ( 0 , \emptyset ) \cr 3 & \quad K \gets \max\{ 1 , \epsilon p_{\max} / |I| \};\ q_i \gets \lfloor p_i / K \rfloor \text{ for } i \in I\quad \triangleright \ \text{the profits scaled down} \cr 4 & \quad V[ 0 ][ s ] \gets 0 \text{ if } s = 0 \text{, else } \infty \cr 5 & \quad \textbf{foreach}\ \text{the } i \text{-th object of } I \text{ and } s \in [ 0 , \textstyle\sum q ]\ \textbf{do}\quad \triangleright\ \text{without it, or with it if } q_i \le s \cr 6 & \qquad V[ i + 1 ][ s ] \gets \min\{ V[ i ][ s ] , V[ i ][ s - q_i ] + v_i \} \cr 7 & \quad s \gets \text{the largest } s \text{ with } V[ |I| ][ s ] \le C \cr 8 & \quad \textbf{return}\ \text{the objects of } V[ |I| ][ s ] \text{, read back from the table, and their profit} \end{array} \]

Vertex cover. The function vertexCoverApprox() (exercise 19.6) takes both the ends of each edge \([ u , v ]\), \(u < v\), whose ends are both out of the cover so far.

Lemma 20.13. vertexCoverApprox() returns a vertex cover \(S\) with \(\lvert S \rvert \le 2 \, \mathit{OPT}\), in \(O( n^2 )\) time on the adjacency matrix.

Proof. An edge whose ends are not both out of \(S\) when it is examined has an end in \(S\), and the edges examined later only add nodes; an edge examined with both ends out of \(S\) puts them in. Hence \(S\) is a cover. The edges that put their ends in \(S\) share no end, since each of them had both ends out of \(S\), i.e., they form a matching \(M\), and \(\lvert S \rvert = 2 \lvert M \rvert\). Any cover has an end of each edge of \(M\), and these ends are distinct; hence \(\mathit{OPT} \ge \lvert M \rvert\). The loop examines the \(n ( n - 1 ) / 2\) pairs \(u < v\). \(\square\)

Knapsack. The function knapsackApprox() (exercise 19.8) is the scheme of Ibarra and Kim 1975: it keeps the objects that fit by themselves, divides their profits by \(K = \max\{ 1 , \epsilon \, p_{\max} / n' \}\), \(n'\) being their number and \(p_{\max}\) their largest profit, and rounds them down; then it finds, by dynamic programming, the least volume \(V[ i ][ s ]\) of the first \(i\) objects of rounded profit \(s\), and returns the set of largest rounded profit within the capacity.

Lemma 20.14. knapsackApprox() returns a set of profit at least \(( 1 - \epsilon ) \, \mathit{OPT}\), in \(O( n^3 / \epsilon )\) time.

Proof. Rounding a profit down to a multiple of \(K\) loses less than \(K\), and therefore less than \(n' K\) on any set, which is \(\epsilon \, p_{\max}\) if \(K > 1\) (and nothing if \(K = 1\), since the profits are integers). The set optimal for the rounded profits is thus within \(\epsilon \, p_{\max} \le \epsilon \, \mathit{OPT}\) of the optimum, since each of the objects kept fits alone. As for the time, the table has a column per rounded profit, at most \(n' \cdot n' / \epsilon\) of them, and a row per object. \(\square\)

20.8 Branch-and-bound

A branch-and-bound visits the tree of the partial solutions of the enumeration of chapter 19 (backtracking), and skips a subtree when a lower bound of the costs in it is not below the best cost found (Montresor 2025, §19.3).

Lemma 20.15 (the bound). If \(\mathit{lb}( S ) \le c( x )\) for each complete solution \(x\) that extends the partial solution \(S\), then skipping \(S\) when

\[ \mathit{lb}( S ) \ge \mathit{minCost} \tag{20.9} \]

loses no solution better than the best found so far, and the visit returns an optimum.

Proof. A solution \(x\) in the subtree of a skipped \(S\) has \(c( x ) \ge \mathit{lb}( S ) \ge \mathit{minCost}\), and the best found so far is at least as good. The solutions not skipped are all compared. \(\square\)

Note that the guarantee holds whatever the order of the visit and the bound, and the time in the worst case stays that of the enumeration; what changes is the number of the nodes in practice, which bbTsp(), littleTsp(), maxWeightClique() and the knapsacks report in *generated, if given.

The salesman, depth first. The function bbTsp() chooses the cities of the circuit one after the other from \(S[ 0 ] = 0\), in increasing order, depth first, starting from the circuit start if one is given (Algorithm 20.18). A child is generated for each city not in \(S\), and visited only if its bound is below the best; a complete circuit is the bound of its last node, i.e., its cost. The function tspLowerBound() computes two bounds, chosen by TspBound. Let \(S = S[ 0 .. i ]\) be the path chosen, \(C_i\) its length and \(R\) the cities out of \(S\). We write \(A\) for the least distance from a city of \(R\) back to \(S[ 0 ]\), \(B\) the least distance from \(S[ i ]\) to a city of \(R\), and \(D_h\), for \(h \in R\), the least cost \(D[ p ][ h ] + D[ h ][ q ]\) of entering and leaving \(h\) over the cities \(p \ne q\) different from \(h\).

Lemma 20.16. Both

\[ \mathit{lb}_{\mathrm{BOOK}}( S ) = C_i + \Bigl\lceil \frac{A + B + \sum_{h \in R} D_h}{2} \Bigr\rceil , \qquad \mathit{lb}_{\mathrm{ONE\_TREE}}( S ) = C_i + A + B + w( T_R ) , \tag{20.10} \]

with \(T_R\) a minimum spanning tree of \(R\) (the ceiling only on integer distances, and the second bound for symmetric distances), satisfy the hypothesis of Lemma 20.15.

Proof. A circuit that extends \(S\) goes on from \(S[ i ]\) through all the cities of \(R\) and back to \(S[ 0 ]\), with \(\lvert R \rvert + 1\) edges. Each city of \(R\) is entered once and left once, which costs at least \(D_h\); the sum of the \(D_h\) counts each edge of the rest of the circuit between two cities of \(R\) twice, and the first and the last edge once, which cost at least \(B\) and \(A\). Hence the rest costs at least half the sum, and the cost is an integer on integer distances. For the 1-tree, the rest is a path through the cities of \(R\), i.e., a spanning tree of \(R\), plus its first and last edge. \(\square\)

Our first bound is that of the text (TspBound::BOOK), which uses the least distances into and out of each city over all the cities, as in its example (\(\mathit{lb} = 18\) for \(S = 1 , 3\) of figure 19.5 of the book; there the least distance \(A\) is taken from \(S[ 0 ]\), which is the same for symmetric distances). We remark that two values of figure 19.6 of the book do not follow from this formula (21 for \(1 , 2 , 3\) and for \(1 , 5\), where it gives 19 and 20), and we found no rule that gives all the values of the figure. With the formula and the circuit \(1 , 4 , 3 , 2 , 5\) of cost 21 to start from, the tree has 25 nodes instead of 23 (30 with no circuit to start from), and it ends with the same circuit \(1 , 3 , 2 , 5 , 4\) of cost 19 (we suspect a slip in the figure, although we cannot exclude another rule). The second bound is that of the 1-tree of Held and Karp 1971 (exercise 19.10), which replaces the sum by the weight of a minimum spanning tree of the cities out of \(S\). Also, spanningTreeWeight() and oneTree() compute the tree of a set of cities and the minimum 1-tree of a city (a minimum spanning tree of the others plus the two least edges of that city), which bounds the optimum from below, since each circuit is a 1-tree.

Algorithm 20.18. The salesman by branch-and-bound with the bound of the text or of the 1-tree (Montresor 2025, §19.3.1 and exercise 19.10).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{tspLowerBound}( D , S , \mathit{how} )\quad \triangleright\ S = ( S[ 0 ] , \ldots , S[ i ] ) \text{, } R \text{ the cities left} \cr 2 & \quad C \gets \text{the cost of the path } S \cr 3 & \quad \textbf{if}\ R = \emptyset\ \textbf{then return}\ C + D[ S[ i ] ][ S[ 0 ] ]\quad \triangleright\ \text{the circuit closed} \cr 4 & \quad A \gets \text{the least } D[ h ][ S[ 0 ] ] \text{, } B \gets \text{the least } D[ S[ i ] ][ h ] \text{, over } h \in R \cr 5 & \quad \textbf{if}\ \mathit{how} = \text{ONE\_TREE} \ \textbf{then return}\ C + A + B + \mathrm{spanningTreeWeight}( D , R ) \cr 6 & \quad D_h \gets \text{the least } D[ p ][ h ] + D[ h ][ q ] \text{ over } p \ne q \text{, both } \ne h \text{, for each } h \in R\quad \triangleright\ \text{the two edges of } h \cr 7 & \quad \textbf{return}\ C + \lceil ( A + B + \textstyle\sum_{h \in R} D_h ) / 2 \rceil \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{bb}( S )\quad \triangleright\ S \text{ a path from the city } 0 \cr 2 & \quad \textbf{foreach}\ c \notin S \text{, by increasing name} \ \textbf{do} \cr 3 & \qquad \mathit{lb} \gets \mathrm{tspLowerBound}( D , S \cdot ( c ) , \mathit{how} );\ \textbf{if}\ \mathit{minCost} \le \mathit{lb} \ \textbf{then continue}\quad \triangleright\ \text{pruned} \cr 4 & \qquad \textbf{if}\ |S| + 1 = n\ \textbf{then}\ ( \mathit{minSol} , \mathit{minCost} ) \gets ( S \cdot ( c ) , \mathit{lb} )\quad \triangleright\ \text{a circuit: the bound is its cost} \cr 5 & \qquad \textbf{else}\ \mathrm{bb}( S \cdot ( c ) ) \cr 6 & \textbf{function}\ \mathrm{bbTsp}( D , \mathit{start} ) \cr 7 & \quad \mathit{minSol} \gets \mathit{start};\ \mathit{minCost} \gets \text{the cost of } \mathit{start} \text{, or } \infty \text{ if it is empty} \cr 8 & \quad \mathrm{bb}( ( 0 ) );\ \textbf{return}\ ( \mathit{minCost} , \mathit{minSol} ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{spanningTreeWeight}( D , V ) \cr 2 & \quad \textbf{return}\ \text{the weight of the tree that } \mathrm{kruskal} \text{ finds on the complete graph on } V \text{ weighted by } D \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{oneTree}( D , r )\quad \triangleright \ \text{a tree on the rest, and two edges of } r \cr 2 & \quad \textbf{return}\ \mathrm{spanningTreeWeight}( D , V \setminus \{ r \} ) + \text{the two least } D[ r ][ h ] \text{, } h \ne r \end{array} \]

The salesman, by the reduction of the matrix. The function littleTsp() (exercise 19.11, the algorithm of Little et al. 1963) branches on including or excluding an edge, the entry 0 of the reduced matrix whose exclusion raises the bound the most, visits the nodes by least bound with a priority queue, and bounds a node by reducing the rows and the columns of its matrix to a least entry 0 (Algorithm 20.19). Subtracting a constant from a row or a column lowers the cost of each circuit by that constant, since a circuit uses one entry of each row and one of each column. Hence the sum of the constants subtracted is a lower bound, and the entries 0 left are the edges that a circuit of that cost would use. Including an edge \(( i , j )\) marks its row and its column as done and sets to \(\infty\) the edge that would close a subcircuit, and excluding it sets \(M[ i ][ j ] = \infty\).

Algorithm 20.19. The algorithm of Little, Murty, Sweeney and Karel (Montresor 2025, exercise 19.11).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{littleTsp}( D )\quad \triangleright \ \text{a node } x \text{: the edges chosen, a reduced matrix } M_x \text{, a bound } \mathit{lb}_x \cr 2 & \quad x \gets \text{the root, with } M_x = D \text{ and } \infty \text{ on the diagonal};\ \mathrm{reduce}( x ) \cr 3 & \quad Q \gets \text{a priority queue holding } x \text{ with priority } \mathit{lb}_x \cr 4 & \quad \textbf{while}\ Q \ne \emptyset\ \textbf{do} \cr 5 & \qquad x \gets \mathrm{deleteMin}( Q );\ \textbf{if}\ x \text{ has } n \text{ edges}\ \textbf{then return} \ \text{its circuit and its cost} \cr 6 & \qquad ( i , j ) \gets \text{the zero of } M_x \text{ whose exclusion costs most, } \min_{h \ne j} M_x[ i ][ h ] + \min_{h \ne i} M_x[ h ][ j ] \cr 7 & \qquad y \gets x \text{ with the edge } ( i , j ) \text{: its row and column done, } \infty \text{ on the edge that would close a subcircuit} \cr 8 & \qquad z \gets x \text{ without the edge } ( i , j ) \text{: } M_z[ i ][ j ] = \infty \cr 9 & \qquad \textbf{foreach}\ c \in \{ y , z \} \text{ that has } n \text{ edges or for which } \mathrm{reduce}( c ) \text{ succeeds} \ \textbf{do}\ \mathrm{insert}( Q , c , \mathit{lb}_c ) \cr 10 & \textbf{function}\ \mathrm{reduce}( x )\quad \triangleright \ \text{false if a row or a column not done has no finite entry} \cr 11 & \quad \text{subtract from each row not done, then from each column not } \text{done, its least entry } \mu \text{, adding } \mu \text{ to } \mathit{lb}_x \end{array} \]

Lemma 20.17. Let the circuits of a node \(x\) be those that contain the edges included in \(x\), the set \(I_x\), and no edge excluded in \(x\). Then \(c( H ) = \mathit{lb}_x + \sum_{e \in H \setminus I_x} M_x[ e ]\) for each circuit \(H\) of \(x\), with \(M_x \ge 0\) on the rows and the columns not done; hence \(\mathit{lb}_x \le c( H )\), and the first node of \(n\) edges extracted in line 5 is an optimal circuit.

Proof. At the root \(I_x\) is empty, \(\mathit{lb}_x = 0\) and \(M_x = D\) before the reduction. Subtracting \(\mu\) from a row not done lowers by \(\mu\) the entry of that row that each circuit of \(x\) uses outside \(I_x\) (there is exactly one, since no edge of \(I_x\) leaves that row), and adds \(\mu\) to \(\mathit{lb}_x\); the same holds for a column, and the minima subtracted leave the entries not negative. In the child \(y\), the edge \(( i , j )\) enters \(I_y\) with \(M_x[ i ][ j ] = 0\), so that the sum does not change, and the edge set to \(\infty\) would close a subcircuit, which no circuit of \(y\) contains. In the child \(z\) no circuit uses \(( i , j )\), and its entry does not appear in the sum. A child whose reduction fails has a row or a column with no finite entry, i.e., no circuit, and is dropped. The circuits of \(x\) are those of \(y\) and those of \(z\); hence the circuits of the root are, at any time, those of the nodes in \(Q\) and those already returned. A node of \(n\) edges has a single circuit, with \(H \setminus I_x = \emptyset\) and \(c( H ) = \mathit{lb}_x\). When such a node is extracted, each other circuit belongs to a node of \(Q\) whose bound is at least \(\mathit{lb}_x\), and therefore costs at least \(\mathit{lb}_x\). \(\square\)

Cliques and knapsacks. The function maxWeightClique() (exercise 19.9) extends a set by the candidates adjacent to all of it, and prunes it when its weight plus that of all its candidates is not above the best. The function knapsackBB() (exercise 19.12) takes the objects by decreasing profit per volume, each in and then out, and prunes a node when the fractional knapsack of the objects left within the capacity left (§13.11) does not beat the best. This is an upper bound of the best profit of the objects left, since the fractional greedy is optimal for the relaxation (Lemma 13.26). The function knapsackBacktrack() is the same visit with the objects in their order and the simple bound, the sum of the profits still to decide. In turn, knapsackGreedy() is the heuristic that takes the objects by decreasing profit per volume while they fit, which is not optimal in general (Algorithm 20.20). The test beyond.knapsack-heuristics checks that the two visits find the optimum of knapsack() and that the greedy finds no more.

Algorithm 20.20. The clique of largest weight, and KNAPSACK by branch-and-bound, by backtracking and by the greedy choice (Montresor 2025, exercises 19.9 and 19.12).

\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{extend}( S , K , \mathit{weight} )\quad \triangleright\ K \text{ the candidates adjacent to all of } S \cr 2 & \quad \textbf{if}\ \mathit{best} < \mathit{weight}\ \textbf{then}\ ( \mathit{best} , \mathit{bestSet} ) \gets ( \mathit{weight} , S ) \cr 3 & \quad \mathit{rest} \gets \text{the weight of the nodes of } K \cr 4 & \quad \textbf{foreach}\ v = K[ a ] \text{, in order}\ \textbf{do} \cr 5 & \qquad \textbf{if}\ \mathit{weight} + \mathit{rest} \le \mathit{best}\ \textbf{then return}\quad \triangleright \ \text{even all of them would not do better} \cr 6 & \qquad \mathit{rest} \gets \mathit{rest} - w( v ) \cr 7 & \qquad \mathrm{extend}( S \cup \{ v \} , \text{the } K[ b ] \text{, } b > a \text{, adjacent to } v , \mathit{weight} + w( v ) ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{bb}( S , i , c , \mathit{profit} )\quad \triangleright\ \text{the objects } i , \ldots , n - 1 \text{ still to decide} \cr 2 & \quad \textbf{if}\ \mathit{best} < \mathit{profit}\ \textbf{then}\ ( \mathit{best} , \mathit{bestSet} ) \gets ( \mathit{profit} , S ) \cr 3 & \quad \textbf{if}\ i = n\ \textbf{or}\ \mathit{profit} + \mathit{frac}( i , c ) \le \mathit{best}\ \textbf{then return}\quad \triangleright\ \text{the fractional bound} \cr 4 & \quad \textbf{if}\ v_i \le c\ \textbf{then}\ \mathrm{bb}( S \cup \{ i \} , i + 1 , c - v_i , \mathit{profit} + p_i )\quad \triangleright \ \text{with } i \text{ first} \cr 5 & \quad \mathrm{bb}( S , i + 1 , c , \mathit{profit} ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{bt}( S , i , c , \mathit{profit} )\quad \triangleright\ \text{as } \mathrm{bb} \text{, with a weaker bound} \cr 2 & \quad \textbf{if}\ \mathit{best} < \mathit{profit}\ \textbf{then}\ ( \mathit{best} , \mathit{bestSet} ) \gets ( \mathit{profit} , S ) \cr 3 & \quad \textbf{if}\ i = n\ \textbf{or}\ \mathit{profit} + \textstyle\sum_{j \ge i} p_j \le \mathit{best}\ \textbf{then return} \cr 4 & \quad \textbf{if}\ v_i \le c\ \textbf{then}\ \mathrm{bt}( S \cup \{ i \} , i + 1 , c - v_i , \mathit{profit} + p_i ) \cr 5 & \quad \mathrm{bt}( S , i + 1 , c , \mathit{profit} ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{knapsackGreedy}( p , v , C )\quad \triangleright\ \text{no bound on its ratio to the optimum} \cr 2 & \quad S \gets \emptyset \cr 3 & \quad \textbf{foreach}\ i \text{, by decreasing } p_i / v_i \text{, that fits in the room left}\ \textbf{do}\ S \gets S \cup \{ i \};\ C \gets C - v_i \cr 4 & \quad \textbf{return}\ ( \textstyle\sum_{i \in S} p_i , S ) \end{array} \]

20.9 Heuristics

A heuristic gives a feasible solution with no guarantee on its cost (Montresor 2025, §19.4); it is judged by its time and by its results in practice, and the contracts of Heuristics.h check that each result is feasible, not that it is "good".

Constructive heuristics. The constructive heuristics of the header are greedy (Algorithm 20.21). The function greedyTsp() keeps the lightest edges that leave each city with at most two of them and close no cycle, as kruskal() does with an MFSET (chapter 11), and so it ends with a Hamiltonian chain, which the edge of its two ends closes; the sort of the \(n ( n - 1 ) / 2\) edges gives \(O( n^2 \log n )\). The function greedySuperstring() (exercise 19.13) is the same greedy on the oriented edges weighed by the overlaps of the strings (overlap( a , b ), the longest suffix of \(a\) that is a prefix of \(b\)), which leaves oriented paths, after dropping the strings contained in another. The function dsatur() (exercise 19.19, Brélaz 1979) colors first the node that sees the most colors among its neighbours, i.e., the most constrained, with the least color not on its neighbours, in \(O( n^3 )\). The function starAlignment() (exercise 19.18, after Gusfield 1993) aligns \(k\) strings against the center, i.e., the string with the largest sum of the global scores against the others. This takes \(O( k^2 \ell^2 )\) time for strings of length at most \(\ell\).

Algorithm 20.21. The greedy heuristics: the salesman, the superstring, the coloring by saturation degree and the star alignment (Montresor 2025, §19.4.1 and exercises 19.13, 19.18 and 19.19).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{greedyTsp}( D )\quad \triangleright \ \text{a Hamiltonian path grown by the shortest edges} \cr 2 & \quad S \gets \emptyset;\ M \gets \text{the MFSET of the } n \text{ cities} \cr 3 & \quad \textbf{foreach}\ [ u , v ] \text{, by increasing } D[ u ][ v ] \text{, until } |S| = n - 1\ \textbf{do} \cr 4 & \qquad \textbf{if}\ u \text{ and } v \text{ have degree } < 2 \text{ in } S \text{ and } \mathrm{find}( M , u ) \ne \mathrm{find}( M , v )\ \textbf{then} \cr 5 & \qquad\quad S \gets S \cup \{ [ u , v ] \};\ \mathrm{merge}( M , u , v ) \cr 6 & \quad \text{add to } S \text{ the edge between the two ends of the path} \cr 7 & \quad \textbf{return}\ ( S , \text{the circuit of } S \text{ from } 0 ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{overlap}( a , b )\quad \triangleright \ \text{the longest suffix of } a \text{ that is a prefix of } b \cr 2 & \quad \textbf{return}\ \text{the largest } \ell \le \min\{ |a| , |b| \} \text{ with } a[ |a| - \ell .. |a| - 1 ] = b[ 0 .. \ell - 1 ] \text{, or } 0 \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{greedySuperstring}( P ) \cr 2 & \quad Q \gets P \text{ less its copies and the strings inside another one} \cr 3 & \quad \textbf{foreach}\ \text{pair } i \ne j \text{, by decreasing } \mathrm{overlap}( Q[ i ] , Q[ j ] )\ \textbf{do}\quad \triangleright \ \text{the strongest merge first} \cr 4 & \qquad \textbf{if}\ i \text{ has no successor, } j \text{ no predecessor, and } \mathrm{find}( i ) \ne \mathrm{find}( j )\ \textbf{then} \cr 5 & \qquad\quad \mathit{next}[ i ] \gets j;\ \mathit{out}[ i ] \gets \textbf{true};\ \mathit{in}[ j ] \gets \textbf{true}; \ \mathrm{merge}( i , j ) \cr 6 & \quad \textbf{return}\ \text{the strings chained by } \mathit{next} \text{ from each start, each overlap written once} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{dsatur}( G )\quad \triangleright \ \text{the saturation of } u \text{: the colors among its neighbors} \cr 2 & \quad c[ v ] \gets \textbf{nil} \text{ for every node } v \cr 3 & \quad \textbf{repeat}\ n \text{ times} \cr 4 & \qquad u \gets \text{the uncolored node of the largest saturation; on a tie, of the } \text{most colored neighbors,} \cr & \qquad\quad \text{then the first} \cr 5 & \qquad c[ u ] \gets \text{the least color absent from the neighbors of } u \cr 6 & \quad \textbf{return}\ c \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{starAlignment}( P )\quad \triangleright \ \text{the centre aligned with every other string} \cr 2 & \quad h \gets \text{the first } i \text{ that maximizes } \textstyle\sum_{j \ne i} \mathrm{score}( P[ i ] , P[ j ] ) \cr 3 & \quad \textbf{return}\ ( h , ( \mathrm{globalAlignment}( P[ h ] , P[ j ] ) : j = 1 , \ldots , k ) ) \end{array} \]

The bisection by buckets. The function minMaxGreedy() (the min-max-greedy of the book) grows the two halves \(V_0\) and \(V_1\) of a bisection in turn, from a node \(a\) in \(V_0\) and a node \(b\) in \(V_1\), each time with the node out of them that has the fewest edges to the other half and, among those, the most to its own (Algorithm 20.22). The structure Buckets of exercise 19.17 keeps, for \(k = 0 , 1\), the nodes not placed by the number \(h\) of their edges to \(V_k\). There bucket( k , h ) is a vector of nodes, whose size is dim( k , h ), each node knows its place in its two buckets, and min( k ) and max( k ) are the least and the largest bucket not empty (Figure 20.3). The function inc( k , u ) moves \(u\) to the next bucket of side \(k\), by taking it out of its bucket (the last node of the bucket fills its place) and appending it to the next one. In turn, choose( k ) scans the least bucket of the other side for the node with the most edges to \(V_k\), contains( u ) is true if \(u\) is still to be placed and count( k , u ) gives its edges to \(V_k\). The size of the cut that results, i.e., the number of edges between the two sides, is cutSize( G , side ).

Figure 20.3. The buckets of the side 0 of a Buckets before and after inc(0,2): the node 2 leaves the bucket 1, where the last node 3 takes its place, and is appended to the bucket 2, and the largest bucket not empty becomes 2.

Lemma 20.18. insert(), remove() and inc() cost \(O( 1 )\) amortized time, and minMaxGreedy() takes \(O( n^2 )\) time on the adjacency matrix, \(O( n )\) choices of \(O( n )\) time each.

Proof. A node leaves a bucket in \(O( 1 )\) by its place, which the node moved into it inherits (line 5 of remove() in Algorithm 20.22). Furthermore, the bounds \(\mathit{min}( k )\) and \(\mathit{max}( k )\) move by a scan (line 6) only when a bucket empties. In minMaxGreedy() all the nodes are inserted at the start, with the count 0, and the counts only grow. Hence \(\mathit{min}( k )\) never decreases, and its scans move it forward at most \(n + 1\) places in all, while \(\mathit{max}( k )\) grows by one at most per inc(), and its scans move it down at most as many places as it grew, plus \(n + 1\). Each node placed updates the counts of its neighbours, \(O( n )\) on the matrix, and each choice scans one bucket. \(\square\)

Algorithm 20.22. The min-max-greedy for the BISECTION, and the removal of a node from a Buckets (Montresor 2025, §19.4.1 and exercise 19.17).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{minMaxGreedy}( G , a , b )\quad \triangleright\ \text{the two sides grow in turn} \cr 2 & \quad B \gets \text{the buckets of all the nodes};\ \mathrm{add}( a , 0 );\ \mathrm{add}( b , 1 );\ k \gets 0 \cr 3 & \quad \textbf{repeat}\ n - 2 \text{ times}\ \mathrm{add}( B.\mathrm{choose}( k ) , k );\ k \gets 1 - k \cr 4 & \quad \textbf{return}\ \mathit{side} \cr 5 & \textbf{procedure}\ \mathrm{add}( u , k )\quad \triangleright\ u \text{ on the side } k \cr 6 & \quad \mathit{side}[ u ] \gets k;\ B.\mathrm{remove}( u ) \cr 7 & \quad \textbf{foreach}\ \text{neighbor } v \text{ of } u \text{ still in } B\ \textbf{do}\ B.\mathrm{inc}( k , v ) \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{procedure}\ \mathrm{remove}( u )\quad \triangleright\ u \text{ leaves both families of buckets} \cr 2 & \quad \mathrm{take}( 0 , u );\ \mathrm{take}( 1 , u ) \cr 3 & \textbf{procedure}\ \mathrm{take}( k , u )\quad \triangleright\ h_k[ u ] \text{ its bucket, } p_k[ u ] \text{ its place there} \cr 4 & \quad B \gets \mathrm{bucket}( k , h_k[ u ] );\ p \gets p_k[ u ] \cr 5 & \quad \text{move the last node } x \text{ of } B \text{ to } B[ p ] \text{, set } p_k[ x ] \gets p \text{, and shorten } B \text{ by one}\quad \triangleright\ O( 1 ) \cr 6 & \quad \textbf{if}\ B = \emptyset\ \textbf{then}\ \text{move } \mathit{min}( k ) \text{ up and } \mathit{max}( k ) \text{ down past the empty buckets,} \cr & \qquad \text{if they were at } h_k[ u ] \text{, within } [ 0 , n ] \end{array} \]

Local search. A local search starts from a solution \(\pi\) and moves to a better solution of its neighbourhood \(I( \pi )\) while there is one. It ends at a local optimum, since the cost decreases strictly at each step and the solutions are finitely many (Montresor 2025, §19.4.2). For the salesman, the neighbourhood \(I_2( \pi )\) of twoOpt() holds the circuits obtained by removing two edges of \(\pi\) that do not touch, and reconnecting the two paths in the only other way, i.e., by reversing the stretch between them (Figure 20.4; Lin 1965), which gives

\[ \lvert I_2( \pi ) \rvert = \frac{n ( n - 1 )}{2} - n , \tag{20.11} \]

the pairs of edges less the \(n\) that touch. Since the change of cost of a move depends only on the four edges that change, a step of the search, which takes the best circuit of the neighbourhood, costs \(O( n^2 )\) (Algorithm 20.23). The function twoOptMove( pi , i , j ) applies one move, reversing \(\pi[ i + 1 .. j ]\), and the costs of the circuits visited go to *trace, if given.

Figure 20.4. A move of twoOpt() on eight cities: the edges \(( 2 , 3 )\) and \(( 5 , 6 )\) of \(\pi\) (dashed), which cross, are replaced by \(( 2 , 5 )\) and \(( 3 , 6 )\) (orange), and the stretch \(3 , 4 , 5\) is reversed.

Algorithm 20.23. The local search on \(I_2\), the size of \(I_k\), and the local search for PARTITION (Montresor 2025, §19.4.2 and exercises 19.15 and 19.16).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{twoOpt}( D , \pi )\quad \triangleright \ \text{the best improvement, until there is none} \cr 2 & \quad c \gets \mathrm{tourCost}( D , \pi ) \cr 3 & \quad \textbf{loop} \cr 4 & \qquad \text{for each } i < j \text{ with } ( \pi[ i ] , \pi[ i + 1 ] ) \text{ and } ( \pi[ j ] , \pi[ ( j + 1 ) \bmod n ] ) \text{ not adjacent,} \cr & \qquad\quad \text{let } c_{ij} \text{ be the cost after replacing them by } ( \pi[ i ] , \pi[ j ] ) \text{ and } ( \pi[ i + 1 ] , \pi[ ( j + 1 ) \bmod n ] ) \cr 5 & \qquad ( b_i , b_j ) \gets \text{the first pair of least } c' = c_{b_i b_j} \cr 6 & \qquad \textbf{if}\ c \le c'\ \textbf{then return}\ \pi \cr 7 & \qquad \pi \gets \mathrm{twoOptMove}( \pi , b_i , b_j );\ c \gets c' \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{kOptNeighbours}( n , k )\quad \triangleright\ \text{by enumeration, for the small } n \cr 2 & \quad E \gets \text{the edges of the circuit } ( 0 , 1 , \ldots , n - 1 ) \cr 3 & \quad c \gets \text{the permutations } s \text{ of } 1 , \ldots , n - 1 \text{ whose circuit } ( 0 ) \cdot s \text{ keeps exactly } n - k \text{ edges of } E \cr 4 & \quad \textbf{return}\ c / 2\quad \triangleright \ \text{each circuit is met in both directions} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{partitionLocalSearch}( A , \mathit{side} )\quad \triangleright\ \Delta \text{ the difference of the two sums} \cr 2 & \quad \textbf{loop} \cr 3 & \qquad M \gets \text{among the moves of one item and the swaps of two items on } \text{opposite sides,} \cr & \qquad\quad \text{the one that leaves the least } | \Delta' | \cr 4 & \qquad \textbf{if}\ | \Delta | \le | \Delta' |\ \textbf{then return} \ \mathit{side}\quad \triangleright\ \text{a local optimum} \cr 5 & \qquad \text{apply } M;\ \Delta \gets \Delta' \end{array} \]

The function kOptNeighbours() (exercise 19.15) counts \(\lvert I_k( \pi ) \rvert\), the circuits that share \(n - k\) edges with \(\pi\), by enumerating all the circuits in \(O( n! )\), which checks (20.11) for \(k = 2\). The function partitionLocalSearch() (exercise 19.16) does the same for PARTITION, with the moves of one element and the swaps of two, each changing the difference of the sums by twice the elements moved, the best move first, in \(O( n^2 )\) per step. Arguably, the classical local search for the bisection, whose moves swap two nodes, is that of Kernighan and Lin 1970; the library does not implement it.

20.10 The fifteen puzzle

In the FIFTEEN PUZZLE (the GIOCO DEL QUINDICI of the book), \(n^2 - 1\) tiles numbered from 1 lie on an \(n \times n\) grid with a hole, a move slides a tile next to the hole into it, and the goal has the tiles in increasing order and the hole last (Montresor 2025, §19.5). A configuration is a Board, the tile of each square by rows, 0 the hole; puzzleGoal() gives the goal and puzzleMoves() the configurations one move away. The function solvePuzzle() is the branch-and-bound of the text, whose nodes are the configurations and whose children are those one move away. The cost of a node \(x\), \(g( x )\), is the number of moves from the root, its lower bound \(h( x )\) is the sum of the distances of the tiles from their places (manhattan()), and the next node visited is the one of least \(f( x ) = g( x ) + h( x )\), by a Fibonacci heap (Figure 20.5). The least level met of each configuration is kept in a map, the parameter Map of solvePuzzle() (std::map by default, or another map of the standard library or of Boost, or a hash table of ADS), which changes the time but not the nodes visited. This is the algorithm A* of Hart, Nilsson and Raphael 1968 (Algorithm 20.24).

Figure 20.5. A configuration of the \(3 \times 3\) puzzle and the moves of the tiles 5 and 8 that reach the goal, with the moves \(g\) from the start and the bound \(h\) of manhattan(); the violet tiles are those out of place, or just moved.

Algorithm 20.24. The fifteen puzzle by A*, by the visit in breadth and by backtracking, and the test of solvability (Montresor 2025, §19.5).

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{solvePuzzle}( B , n )\quad \triangleright \ \text{A* with the Manhattan distance} \cr 2 & \quad \textbf{if}\ \textbf{not}\ \mathrm{solvable}( B , n ) \ \textbf{then return nil} \cr 3 & \quad \mathit{best}[ B ] \gets 0;\ Q \gets \text{a min-heap holding } B \text{ with priority } \mathrm{manhattan}( B ) \cr 4 & \quad \textbf{while}\ Q \ne \emptyset\ \textbf{do} \cr 5 & \qquad x \gets \mathrm{deleteMin}( Q );\ \textbf{if}\ \mathit{best}[ x ] < g( x )\ \textbf{then continue}\quad \triangleright \ \text{an older copy of } x \cr 6 & \qquad \textbf{if}\ x \text{ is the goal}\ \textbf{then return} \ \text{the moves from } B \text{ to } x \cr 7 & \qquad \textbf{foreach}\ y \in \mathrm{puzzleMoves}( x ) \text{ with } g( x ) + 1 < \mathit{best}[ y ]\ \textbf{do}\quad \triangleright\ \mathit{best} \text{ is } \infty \text{ where unset} \cr 8 & \qquad\quad \mathit{best}[ y ] \gets g( x ) + 1;\ \mathrm{insert}( Q , y , \mathit{best}[ y ] + \mathrm{manhattan}( y ) ) \cr 9 & \quad \textbf{return nil} \end{array} \]

*Lemma 20.19 (A with a consistent bound).** If \(h\) is 0 at the goal and

\[ h( x ) \le 1 + h( y ) \quad \text{for each move from } x \text{ to } y , \tag{20.12} \]

then the first goal extracted from the queue is reached in the fewest moves, and each configuration is expanded at most once.

Proof. A move changes the place of one tile by one square, and so changes manhattan() by at most 1, which is (20.12). Summing (20.12) along a path to the goal shows that \(h\) never exceeds the moves left, and adding \(g\) shows that \(f\) never decreases along a path. Let \(\delta( y )\) be the fewest moves from the start to \(y\). We first show that a configuration \(y\) is extracted (and not skipped as stale) only with \(g( y ) = \delta( y )\). Otherwise, on a shortest path to \(y\) let \(z\) be the first configuration not yet expanded with \(g( z ) = \delta( z )\); its predecessor was, and so \(z\) is in the queue with \(g( z ) = \delta( z )\) and \(f( z ) = \delta( z ) + h( z ) \le \delta( y ) + h( y ) < g( y ) + h( y )\) by (20.12) along the path, and \(z\) would have been extracted before \(y\). Hence each configuration \(y\) is expanded once: after it is expanded with \(g( y ) = \delta( y )\), the map holds \(\delta( y )\), and any later entry of \(y\) has \(g > \delta( y )\), since line 8 inserts \(y\) only with a level smaller than the one stored, hence once with the level \(\delta( y )\); line 5 skips such an entry. Applied to the first goal \(x\) extracted, \(g( x ) = \delta( x )\), i.e., it is reached in the fewest moves. \(\square\)

We made the map a parameter of solvePuzzle(), std::map by default, and the same search therefore runs with the maps of the standard library, of Boost or of the library (e.g., FlatHashTable) and visits the same nodes; if a pointer visited is given, the function counts there the nodes extracted. Beyond the text, two searches work with any goal, e.g., the spiral one of puzzleSpiralGoal() (Algorithm 20.24). The function puzzleBFS() is the case \(h = 0\), the visit in breadth, whose first goal reached is one of the fewest moves, and which examines many more configurations than A*. In turn, puzzleDFS() is the backtracking that goes back when a configuration is already on the current path or the moves exceed a bound, and it finds a solution of at most that many moves if there is one, not necessarily the shortest.

\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{puzzleBFS}( B , \mathit{goal} ) \cr 2 & \quad p[ B ] \gets B;\ Q \gets ( B ) \cr 3 & \quad \textbf{while}\ Q \ne \emptyset\ \textbf{do} \cr 4 & \qquad u \gets \mathrm{dequeue}( Q ) \cr 5 & \qquad \textbf{if}\ u = \mathit{goal}\ \textbf{then return} \ \text{the path from } B \text{ to } u \text{ by } p \cr 6 & \qquad \textbf{foreach}\ v \in \mathrm{puzzleMoves}( u ) \text{ with no } p[ v ]\ \textbf{do}\ p[ v ] \gets u; \ \mathrm{enqueue}( Q , v ) \cr 7 & \quad \textbf{return nil} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{extend}( S )\quad \triangleright \ \text{started with } S = ( B ) \cr 2 & \quad \textbf{if}\ \text{the last of } S \text{ is } \mathit{goal} \ \textbf{then return true} \cr 3 & \quad \textbf{if}\ |S| > \mathit{nmax} \ \textbf{then return false}\quad \triangleright\ \mathit{nmax} \text{ moves made} \cr 4 & \quad \textbf{foreach}\ v \in \mathrm{puzzleMoves}( \text{the last of } S ) \text{ with } v \notin S\ \textbf{do} \cr 5 & \qquad \textbf{if}\ \mathrm{extend}( S \cdot ( v ) ) \ \textbf{then return true} \cr 6 & \quad \textbf{return false} \end{array} \]
\[ \begin{array}{rl} 1 & \textbf{function}\ \mathrm{solvable}( B , n )\quad \triangleright \ \text{a move keeps the parity of the quantity below} \cr 2 & \quad \mathit{inv} \gets \text{the pairs } p < q \text{ of tiles, the hole left out, with } B[ q ] < B[ p ] \cr 3 & \quad \textbf{return}\ \mathit{inv} \text{ even if } n \text{ is odd, else } \mathit{inv} + n - 1 - r \text{ even, } r \text{ the row of the hole} \end{array} \]

Lemma 20.20. Let \(I\) be the number of the inversions of the tiles read by rows, the hole left out, and \(r\) the row of the hole. A move keeps the parity of \(I\) when \(n\) is odd, and that of \(I + r\) when \(n\) is even; hence half of the configurations cannot reach the goal.

Proof. A move of the hole along a row leaves the order of the tiles unchanged. A move along a column moves one tile past the \(n - 1\) tiles between its two places in the order by rows, which changes \(I\) by an amount of the parity of \(n - 1\), and changes \(r\) by one. With \(n\) odd, \(n - 1\) is even; with \(n\) even, \(I\) and \(r\) change parity together. Exchanging two tiles changes the parity of \(I\) and leaves \(r\), and it therefore maps the configurations of one parity one to one onto those of the other. The two classes thus have the same size, and those of the parity other than that of the goal cannot reach it. \(\square\)

The function solvable() compares that parity with the one of the goal (Johnson and Story 1879), which is also sufficient, as they proved; solvePuzzle() calls it first, and answers nothing on a configuration that cannot reach the goal, instead of exhausting the half of the configurations that it can reach.

20.11 The interface

We collect here, header by header, the declarations of the namespace ADS that a user calls in this chapter, without the contracts, the documentation and the members that only the implementation uses; each block points to the section that describes its functions, and the example at the end shows the main structures at work. The program of the example compiles against the headers as it stands, and its assertions hold.

Domino.h (§20.1).

// declarations of <ADS/complexity/Domino.h>
struct Tile
{
 int up , right , down , left;
 };
using Tiling = std::vector< std::vector< int > >;
bool legalTiling( const std::vector< Tile > & D , int n , const Tiling & T );
std::optional< Tiling > squareTiling( const std::vector< Tile > & D , int n );
bool linearTiling( const std::vector< Tile > & D , long n );

EasyCases.h (§20.5).

// declarations of <ADS/complexity/EasyCases.h>
int literalNode( int l );
std::optional< std::vector< bool > > twoSat( const Cnf & F , int n );
std::optional< std::vector< int > > twoColoring( const Adjacency & G );
std::vector< std::pair< int , int > >
bipartiteMatching( int p , int q ,
                   const std::vector< std::pair< int , int > > & E );
Adjacency intervalGraph( const std::vector< std::pair< long , long > > & I );
int intervalClique( const std::vector< std::pair< long , long > > & I );

Nondeterminism.h (§20.2).

// declarations of <ADS/complexity/Nondeterminism.h>
class Chooser
{
 public:
 int choice( int k );
 template< class A >
 bool run( A && alg , long * runs = nullptr );
 std::vector< int > choices( void ) const;
 };

Problems.h (§20.1).

// declarations of <ADS/complexity/Problems.h>
using Adjacency = std::vector< std::vector< bool > >;
using Clause = std::vector< int >;
using Cnf = std::vector< Clause >;
using Nodes = std::vector< int >;
bool cliqueCertificate( const Adjacency & G , const Nodes & S , int k );
std::optional< Nodes > clique( const Adjacency & G , int k );
std::optional< Nodes > independentSet( const Adjacency & G , int k );
std::optional< Nodes > vertexCover( const Adjacency & G , int k );
std::optional< std::vector< int > > coloring( const Adjacency & G , int k );
std::optional< Nodes > bisection( const Adjacency & G , int k );
template< class T >
bool tspCertificate( const std::vector< std::vector< T > > & D , T k ,
                     const Nodes & P );
template< class T >
std::optional< Nodes > tsp( const std::vector< std::vector< T > > & D , T k );
std::optional< Nodes > hamiltonianCircuit( const Adjacency & G );
std::optional< Nodes > hamiltonianCycle( const Adjacency & G );
std::optional< Nodes > hamiltonianPath( const Adjacency & G , int r = -1 ,
                                        int t = -1 );
std::optional< Nodes > hamiltonianChain( const Adjacency & G );
std::optional< Nodes > longestPath( const Adjacency & G , int r , int t ,
                                    int k );
int longestPathDag( const Adjacency & G , int r , int t );
std::optional< std::vector< std::pair< int , int > > >
boundedSpanningTree( const Adjacency & G , int k );
bool satCertificate( const Cnf & F , const std::vector< bool > & x );
std::optional< std::vector< bool > > satisfiable( const Cnf & F , int n );
std::optional< std::vector< int > >
lp01( const std::vector< std::vector< long > > & A ,
      const std::vector< long > & b , int n );
std::optional< Nodes > subsetSumExists( const std::vector< long > & A ,
                                        long k );
std::optional< Nodes > partition( const std::vector< long > & A );
std::optional< Nodes > knapsackDecision( const std::vector< long > & p ,
                                         const std::vector< long > & v ,
                                         long C ,
                                         long k );
std::optional< std::vector< int > >
multiprocessorScheduling( const std::vector< long > & t , int m , long d );
std::optional< Nodes >
exactCover3( const std::vector< std::array< int , 3 > > & Y , int m );
std::optional< Nodes >
threeDimensionalMatching( const std::vector< std::array< int , 3 > > & M ,
                          int q );
std::optional< std::vector< long > > bribes( std::vector< long > M ,
                                             const std::vector< bool > & ps );

Reductions.h (§20.4).

// declarations of <ADS/complexity/Reductions.h>
int tileVar( int h , int i , int j , int n );
std::pair< Adjacency , int > dominoToClique( const std::vector< Tile > & D ,
                                            int n );
Cnf dominoToSat( const std::vector< Tile > & D , int n );
std::pair< std::vector< std::vector< long > > , std::vector< long > >
dominoToLp01( const std::vector< Tile > & D , int n );
Adjacency complement( const Adjacency & G );
std::vector< std::vector< long > > hamiltonToTsp( const Adjacency & G );
long halfSum( const std::vector< long > & A );
Adjacency cycleToPath( const Adjacency & G );
Adjacency cycleToChain( const Adjacency & G );
std::vector< Point > sortToHull( const std::vector< long > & a );

Approximation.h (§20.7).

// declarations of <ADS/intractable/Approximation.h>
std::vector< int > firstFit( const std::vector< long > & A , long k ,
                             bool decreasing = false );
template< class T >
T tourCost( const std::vector< std::vector< T > > & D , const Nodes & S );
template< class T >
Nodes deltaTsp( const std::vector< std::vector< T > > & D );
std::vector< std::vector< long > > tspGap( const Adjacency & G , long s );
std::pair< long , Nodes > apSubsetSum( const std::vector< long > & A , long k ,
                                      int h );
std::pair< long , Nodes > knapsackApprox( const std::vector< long > & p ,
                                         const std::vector< long > & v ,
                                         long C ,
                                         double eps );
Nodes vertexCoverApprox( const Adjacency & G );

BranchAndBound.h (§20.8).

// declarations of <ADS/intractable/BranchAndBound.h>
enum class TspBound { BOOK , ONE_TREE };
template< class T >
T spanningTreeWeight( const std::vector< std::vector< T > > & D ,
                      const Nodes & V );
template< class T >
T oneTree( const std::vector< std::vector< T > > & D , int r );
template< class T >
T tspLowerBound( const std::vector< std::vector< T > > & D , const Nodes & S ,
                 TspBound how = TspBound::BOOK );
template< class T >
std::pair< T , Nodes >
bbTsp( const std::vector< std::vector< T > > & D , const Nodes & start = {} ,
       TspBound how = TspBound::BOOK , long * generated = nullptr );
template< class T >
std::pair< T , Nodes > littleTsp( const std::vector< std::vector< T > > & D ,
                                 long * generated = nullptr );
std::pair< long , Nodes > maxWeightClique( const Adjacency & G ,
                                          const std::vector< long > & w ,
                                          long * generated = nullptr );
std::pair< long , Nodes > knapsackBB( const std::vector< long > & p ,
                                     const std::vector< long > & v , long C ,
                                     long * generated = nullptr );
std::pair< long , Nodes > knapsackBacktrack( const std::vector< long > & p ,
                                            const std::vector< long > & v ,
                                            long C ,
                                            long * generated = nullptr );
std::pair< long , Nodes > knapsackGreedy( const std::vector< long > & p ,
                                         const std::vector< long > & v ,
                                         long C );

FifteenPuzzle.h (§20.10).

// declarations of <ADS/intractable/FifteenPuzzle.h>
using Board = std::vector< int >;
Board puzzleGoal( int n );
int manhattan( const Board & B , int n );
std::vector< Board > puzzleMoves( const Board & B , int n );
Board puzzleSpiralGoal( int n );
std::optional< std::vector< Board > > puzzleBFS( const Board & B ,
                                                 const Board & goal , int n ,
                                                 long * visited = nullptr );
std::optional< std::vector< Board > >
puzzleDFS( const Board & B , const Board & goal , int n , int nmax );
bool solvable( const Board & B , int n );
template< class Map = std::map< Board , int > >
std::optional< std::vector< Board > > solvePuzzle( const Board & B , int n ,
                                                   long * visited = nullptr );

Heuristics.h (§20.9).

// declarations of <ADS/intractable/Heuristics.h>
template< class T >
std::pair< std::vector< std::pair< int , int > > , Nodes >
greedyTsp( const std::vector< std::vector< T > > & D );
Nodes twoOptMove( Nodes pi , int i , int j );
template< class T >
Nodes twoOpt( const std::vector< std::vector< T > > & D , Nodes pi ,
              std::vector< T > * trace = nullptr );
long kOptNeighbours( int n , int k );
std::vector< int > partitionLocalSearch( const std::vector< long > & A ,
                                         std::vector< int > side );
class Buckets
{
 public:
 explicit Buckets( int n );
 void insert( int u );
 void remove( int u );
 void inc( int k , int u );
 bool contains( int u ) const;
 int count( int k , int u ) const;
 const Nodes & bucket( int k , int h ) const;
 int dim( int k , int h ) const;
 int min( int k ) const;
 int max( int k ) const;
 int choose( int k ) const;
 };
std::vector< int > minMaxGreedy( const Adjacency & G , int a , int b );
int cutSize( const Adjacency & G , const std::vector< int > & side );
int overlap( const std::string & a , const std::string & b );
std::string greedySuperstring( const std::vector< std::string > & P );
std::pair< int , std::vector< std::pair< std::string , std::string > > >
starAlignment( const std::vector< std::string > & P );
std::vector< int > dsatur( const Adjacency & G );

Pseudopolynomial.h (§20.6).

// declarations of <ADS/intractable/Pseudopolynomial.h>
template< class Bits = std::vector< bool > >
bool subsetSumDP( const std::vector< long > & A , long k ,
                  std::vector< std::vector< bool > > * rows = nullptr );
std::optional< Nodes > subsetSumSet( const std::vector< long > & A , long k );
std::optional< Nodes > partitionDP( const std::vector< long > & A );
std::optional< std::vector< int > >
schedulingDP( const std::vector< long > & t , int m , long d );
struct Piece
{
 int program;
 double start , end;
 };
std::pair< double , std::vector< std::vector< Piece > > >
mcNaughton( const std::vector< double > & t , int m );
std::optional< std::vector< std::vector< Piece > > >
realTimeScheduling( const std::vector< double > & C ,
                    const std::vector< double > & T , int m );
std::optional< std::vector< int > > bottino( const std::vector< long > & P );
#include "ADS/complexity/Nondeterminism.h"
#include "ADS/complexity/Problems.h"
#include "ADS/intractable/Approximation.h"
#include <cassert>

int main( void )
{
 ADS::Adjacency G( 4 , std::vector< bool >( 4 , true ) );
 G[ 0 ][ 3 ] = G[ 3 ][ 0 ] = false;  // K4 less an edge
 assert( ADS::clique( G , 3 ) && ! ADS::clique( G , 4 ) );
 ADS::Chooser ch;  // guess a root of 49
 const bool yes = ch.run( []( ADS::Chooser & c ) {
  const int x = c.choice( 10 );
  return( x * x == 49 );
  } );
 assert( yes && ( ch.choices() == std::vector< int >{ 7 } ) );
 auto [ profit , S ] =
   ADS::knapsackApprox( { 60 , 100 , 120 } , { 10 , 20 , 30 } , 50 , 0.1 );
 assert( profit >= 198 );  // ( 1 - 0.1 ) 220
 }

20.12 Discussion and references

We followed Montresor 2025 closely: the classes P and NP, the nondeterministic algorithms, the reductions and the chain from BOUNDED TILING are those of Montresor 2025, chapter 18, and the strategies for the intractable problems those of its chapter 19. As is well known, the NP-completeness of SATISFIABILITY is due to Cook 1971 and, independently, to Levin 1973, the chain of the classical problems to Karp 1972, and the tiles to Wang 1961; Garey and Johnson 1979 remains the reference for the problems and their reductions, and Garey and Johnson 1978 for the strong NP-completeness. The linear algorithm for 2-SATISFIABILITY is that of Aspvall, Plass and Tarjan 1979. Among the strategies, the rule of McNaughton 1959 is one of the first results on preemptive scheduling; the analysis of the first fit is that of Johnson et al. 1974, the double tree for the triangular salesman that of Rosenkrantz, Stearns and Lewis 1977, and the approximation scheme of the knapsack that of Ibarra and Kim 1975. Also, the branch-and-bound by the reduction of the matrix is that of Little et al. 1963, and the bound of the 1-tree that of Held and Karp 1971; the neighbourhoods \(I_k\) go back to Lin 1965, and the local search for the bisection to Kernighan and Lin 1970. The coloring by saturation degree is due to Brélaz 1979, the star alignment to Gusfield 1993, the algorithm A* to Hart, Nilsson and Raphael 1968, and the parity of the fifteen puzzle to Johnson and Story 1879. The set cover, of which the cover of a segment of §13.11 is the case on the line, is approximated within \(\ln n\) by the greedy of Chvátal 1979. All the headers of the two areas are covered by the chapter.

20.13 Exercises

Each exercise names the test of the library that solves it (run it with ctest -R <name>).

  1. Simulate a nondeterministic algorithm by the enumeration of its sequences of choices, and count the runs. Test: ch18.sec18.2.nondeterminism.
  2. Write the certificates of CLIQUE, TRAVELING SALESMAN and SATISFIABILITY, and decide the three problems by enumeration. Test: ch18.sec18.examples.
  3. Decide whether a graph can be colored with \(k\) colors, trying each coloring once up to a renaming of the colors (Montresor 2025, exercise 18.6). Test: ch18.ex18.6.
  4. Decide KNAPSACK by an enumeration pruned on the volume. Test: ch18.ex18.5.
  5. Decide EXACT COVER BY 3-SETS by an enumeration that skips the sets that meet those chosen. Test: ch18.ex18.7.
  6. Give the bribes to the politicians so that one party gets twice the other. Tests: ch18.ex18.1, ch18.ex18.4.
  7. Reduce BOUNDED TILING to CLIQUE, to SATISFIABILITY and to 0-1 INTEGER PROGRAMMING, and check the answers on the coverings found by enumeration. Test: ch18.sec18.7.domino.
  8. Reduce CLIQUE to INDEPENDENT SET, HAMILTONIAN CIRCUIT to TRAVELING SALESMAN and PARTITION to the numerical problems. Test: ch18.sec18.7.reductions.
  9. Reduce INDEPENDENT SET to VERTEX COVER. Test: ch18.ex18.11.
  10. Reduce the directed Hamiltonian circuit to the directed Hamiltonian path, and to the unoriented one. Tests: ch18.ex18.13, ch18.ex18.14.
  11. Find the longest path of an acyclic graph in polynomial time, and reduce the Hamiltonian path to the longest path of a general graph. Test: ch18.ex18.15.
  12. Decide the linear tiling in \(O( m^2 )\) time, whatever \(n\) is. Test: ch18.sec18.5.linear-tiling.
  13. Prove that the convex hull costs \(\Omega( n \log n )\) by a reduction of sorting. Test: ch18.sec18.5.hull-sort.
  14. Solve 2-SATISFIABILITY in linear time by the strongly connected components of the graph of the implications. Test: conclusion.table19.1.sat.
  15. Find the largest clique of an interval graph. Test: conclusion.intervals.
  16. Solve SUBSET SUM in pseudopolynomial time with one row of bits, and read a subset back from the table. Test: ch19.sec19.1.subset-sum.
  17. Schedule \(n\) programs on \(m\) processors by the dynamic programming on the loads, and by the rule of McNaughton when they may be interrupted. Tests: ch19.ex19.2, ch19.ex19.3.
  18. Share a loot among three thieves. Test: ch19.ex19.5.
  19. Show that the first fit uses fewer than twice the boxes of the optimum. Test: ch19.sec19.2.bin-packing.
  20. Approximate the triangular salesman within a factor 2 by the double tree, and show that no constant factor is possible in general. Tests: ch19.sec19.2.delta-tsp, ch19.sec19.2.gap.
  21. Approximate SUBSET SUM within \(1 / ( h + 1 )\). Test: ch19.sec19.2.ap-subset-sum.
  22. Approximate VERTEX COVER within a factor 2, and KNAPSACK within \(1 - \epsilon\) in time polynomial in \(n\) and \(1 / \epsilon\). Tests: ch19.ex19.6, ch19.ex19.8.
  23. Solve the salesman by branch-and-bound with the bound of the text and with the bound of the 1-tree. Tests: ch19.sec19.3.bb-tsp, ch19.ex19.10.
  24. Solve the salesman by the algorithm of Little, Murty, Sweeney and Karel. Test: ch19.ex19.11.
  25. Find a clique of largest weight by branch-and-bound. Test: ch19.ex19.9.
  26. Solve KNAPSACK by branch-and-bound with the fractional bound, and compare the nodes with those of the backtracking. Test: ch19.ex19.12.
  27. Build a circuit by the greedy on the edges and improve it by the local search on \(I_2\). Tests: ch19.sec19.4.greedy-tsp, ch19.sec19.4.local-search.
  28. Count the neighbourhood \(I_k\) of a circuit. Test: ch19.ex19.15.
  29. Realize the structure with buckets of the min-max-greedy, and use it for the bisection. Tests: ch19.ex19.17, ch19.sec19.4.bisection.
  30. Find a common superstring by the greedy on the overlaps, and color a graph by saturation degree. Tests: ch19.ex19.13, ch19.ex19.19.
  31. Solve the fifteen puzzle in the fewest moves by A* with the bound of the distances, and decide whether a configuration can reach the goal. Test: ch19.sec19.5.fifteen.