11 Dynamic programming over the decompositions
This section obtains exact algorithms by running dynamic programs over the path decompositions of Theorem 1.5. The running time of such a program is exponential in the width of the decomposition, so a smaller width bound gives a faster algorithm directly.
11.1 Problems, dynamic programs and the decompositions used
Max \((r,2)\)-CSP.
An instance of Max \((r,2)\)-CSP consists of a simple graph \(G\), the constraint graph, whose vertices are the variables; a score function \(s_v\colon[r]\to\mathbb{R}\) for every variable \(v\); and a score function \(s_{uv}\colon[r]^2\to\mathbb{R}\) for every edge \(uv\in E(G)\). The task is to find an assignment \(\varphi\colon V(G)\to[r]\) maximizing \[\sum_{v\in V(G)}s_v(\varphi(v))+\sum_{uv\in E(G)}s_{uv}(\varphi(u),\varphi(v)).\] Following Scott and Sorkin we write \(r\) for the domain size. We write \(n\) for the number of variables and \(m\) for the number of constraints. Several constraints on the same pair of variables are added into one, so the constraint graph is simple and \(|E(G)|\le m\). Max 2-SAT (\(r=2\), with \(m\) the number of \(2\)-clauses; unit clauses become vertex scores) and Max \(k\)-Colorable Subgraph (\(r=k\)) are special cases.
Semiring, ring and polynomial versions.
Let \((\mathbb S,\oplus,\otimes)\) be a commutative semiring. The semiring version of the problem has score functions with values in \(\mathbb S\) and asks for \[\begin{equation*} \tag{11.1} Z=\bigoplus_{\varphi\colon V(G)\to[r]}\ \bigotimes_{v\in V(G)}s_v(\varphi(v))\otimes \bigotimes_{uv\in E(G)}s_{uv}(\varphi(u),\varphi(v)). \end{equation*}\] More generally, each variable \(v\) may have its own finite domain \(D_v\) in place of \([r]\); the score functions are then defined on \(D_v\) and on \(D_u\times D_v\), and (11.1) runs over the assignments with \(\varphi(v)\in D_v\) for every \(v\). Max \((r,2)\)-CSP is the case of the semiring \((\mathbb{R}\cup\{-\infty\},\max,+)\); counting the solutions of a binary constraint satisfaction problem is the case \((\mathbb{N},+,\times)\) with scores in \(\{0,1\}\). Scott and Sorkin (Scott and Sorkin 2009) call the version over a commutative ring the ring CSP (RCSP), and the version over a polynomial ring the polynomial CSP (PCSP). These cover, among others, counting cuts of every size and the Ising partition function (Scott and Sorkin 2009). When we say that such a version is solved in time \(T\), we mean \(T\) semiring operations; for the applications just named, each ring element has a representation of polynomial size and each operation takes polynomial time.
The following dynamic programs are standard; we state them for path decompositions in the form needed below. Part (a) is the dynamic program behind (Berendsohn, Kozma, and Marx 2021 Lemmas 2 and 4) and (Scott and Sorkin 2009, sec. 9); the \(3^{w}\) dynamic program for dominating sets is due, for tree decompositions, to van Rooij, Bodlaender and Rossmanith (Rooij, Bodlaender, and Rossmanith 2009), and part (c) is standard and folklore. In this section, vertex weights are real numbers.
Lemma 11.1 (dynamic programs over a path decomposition). Let \(G\) be a graph with \(n\) vertices, given with a path decomposition of width \(w\) in interval form.
(a) For a semiring version with constraint graph \(G\) and domains of size at most \(r\), the value \(Z\) of (11.1) can be computed with \(O(n\,(w+2)\,r^{w+1})\) semiring operations, keeping \(O(r^{w+1})\) semiring elements at a time; for Max \((r,2)\)-CSP with constraint graph \(G\), an optimal assignment can be found in time and space \(r^{w+1}\mathop{\mathrm{poly}}(n)\).
(b) One can count the dominating sets of each size, find a dominating set of minimum weight and count the dominating sets of minimum weight, in time and space \(3^{w+1}\mathop{\mathrm{poly}}(n)\).
(c) One can count the independent sets, find a maximum weight independent set and count the maximum weight independent sets in time and space \(2^{w+1}\mathop{\mathrm{poly}}(n)\).
Each part keeps a table indexed by the partial solutions on the vertices of the current bag along a nice sequence of introduce and forget steps.
The decompositions.
Most results of this section run one of the dynamic programs of Lemma 11.1, the others algorithms from the literature, over a path decomposition. The decompositions are in interval form and are computed in polynomial time by the deterministic algorithm of Theorem 10.1(b); when we cite Theorem 1.5 below, we mean this algorithm. For a graph \(G\) the width is at most \(W(G)+\rho(n)\), with \(\rho(n)=o(n)\), where \(W\) is one of the following bounds (Theorems 8.1, 7.1, 7.2 and 1.3 and Corollary 1.4):
\(c_{3}n\) if \(\Delta(G)\le3\), with \(c_{3}=\frac3{4\pi}\arccos\frac56 <0.1398222\);
\(F_4n\), \(F_3n_3+0.2575\,n_4\) or \(\frac5{32}n_3+\frac14n_4\) if \(\Delta(G)\le4\), with \(F_4<0.24577198\) (Proposition 6.9); we write \(\beta_4(G):=\min\{F_4n,\ F_3n_3+0.2575\,n_4,\ \frac5{32}n_3+\frac14n_4\}\);
\(a_3n_3+a_4n_4+a_5n_5\) for each of the triples \(\mathsf{P},\mathsf{R},\mathsf{S}\) if \(\Delta(G)\le5\);
\(\beta(G):=\sum_{d\ge3}a_dn_d\) for every \(G\), with the coefficients \(a_d\) of Theorem 1.3;
\(\frac7{48}m\) for every \(G\).
Running Theorem 1.5 once for each of several bounds and keeping the narrowest decomposition realizes their minimum, for instance \(\beta_4(G)\). Since the width is at most \(W(G)\) plus the remainder, a dynamic program with \(c^{w+1}\mathop{\mathrm{poly}}(n)\) steps runs in time \(c^{W(G)+o(n)}\mathop{\mathrm{poly}}(n)\) (with \(o(m)\) for the bound \(\frac7{48}m\)), for every constant \(c\) and also for \(c=r\) growing with the input.
Two parts of Theorem 11.3 evaluate a bound on the final graph \(R\) of a maximal sequence of reduction operations (Definition 4.2) applied to \(G\); then \(R\) is empty or has minimum degree at least \(3\) by (RP3). Reduction operations increase no degree by (RP1), so they do not increase the number of edges either. Lemma A.28, with no vertex deletions, turns a path decomposition of \(R\) of width \(w\) in interval form into one of \(G\) of width at most \(w+3\log_2n+1\), in polynomial time.
11.2 Pathwidth in terms of the vertices of degree three
Theorem 8.1 bounds the pathwidth of a graph of maximum degree \(3\) in terms of the number of all its vertices. Some algorithms, such as the algorithm for counting dominating sets of Section 13, need a bound in the number of vertices of degree \(3\) alone; the polynomial-space analyses of Section 12 use the separator version of such a bound in Lemma C.2. The next lemma converts Theorem 8.1 into such a bound: the vertices of degree at most \(2\) add only a term of order \(\log n_3\) to the width.
Lemma 11.2 (pathwidth by the number of degree-\(3\) vertices). There is a nondecreasing function \(\rho\colon\mathbb{N}\to\mathbb{R}\) with \(\rho(k)=o(k)\) such that every graph \(H\) with \(\Delta(H)\le3\) satisfies \[\mathop{\mathrm{pw}}(H)\le c_{3}\,n_3(H)+\rho\bigl(n_3(H)\bigr).\] A path decomposition of this width can be computed in polynomial time.
The proof, in Appendix A.7.1, removes the trees outside the \(2\)-core, suppresses the vertices of degree \(2\) of the core, and applies Theorem 8.1 to the resulting cubic multigraph; putting back the suppressed paths costs \(2\) in the width, and the trees \(O(\log n_3)\).
11.3 Max \((r,2)\)-CSP and its relatives
The first theorem is the most direct consequence of the width bounds: Max \((r,2)\)-CSP, and every semiring version of it, is solved by the dynamic program of Lemma 11.1(a) over the narrowest available decomposition of the constraint graph. In terms of the number \(m\) of constraints, this lowers the exponent of the previous record \(r^{(13/75)m+o(m)}\) (Scott and Sorkin 2007 Cor. 21) to \(\frac7{48}m+o(m)\). Part (1) of the theorem is the most general statement; the other parts are stated in the parameters of the previous records. Part (4) uses the average degree \(\bar d:=2|E(G)|/n\) of the constraint graph \(G\) and the concave function \(A\colon[0,\infty)\to\mathbb{R}\) defined before Corollary 9.15: \(A(x)=\frac7{96}x\) for \(0\le x\le6\), and \(A\) interpolates the coefficients \(a_d\) linearly between consecutive integers \(d\ge6\).
Theorem 11.3 (Max \((r,2)\)-CSP). Let \(G\) be the constraint graph of an instance of Max \((r,2)\)-CSP, or of a semiring version, with \(n\) variables and \(m\) constraints. The instance can be solved in time and space
(1) \(O^{*}\bigl(r^{\beta(R)+o(n)}\bigr)\) for the final graph \(R\) of some maximal sequence of reduction operations applied to \(G\), and hence \(O^{*}\bigl(r^{\beta(G)+o(n)}\bigr)\);
(2) \(O^{*}\bigl(r^{(7/48)m+o(m)}\bigr)\);
(3) \(O^{*}\bigl(r^{c_{3}n_3+o(n)}\bigr)\) if \(\Delta(G)\le3\), and \(O^{*}\bigl(r^{\beta_4(G)+o(n)}\bigr)\) and \(O^{*}\bigl(r^{3F_4m/(2+16F_4)+o(m)}\bigr)\) if \(\Delta(G)\le4\);
(4) \(O^{*}\bigl(r^{n\,A(\bar d)+o(n)}\bigr)\), and hence \[O^{*}\Bigl(r^{(1-\frac{111}{28(\bar d+1)})n+o(n)}\Bigr)\ \text{if }\bar d\ge7, \qquad O^{*}\Bigl(r^{(1-\frac{4}{\bar d+1})n+o(n)}\Bigr)\ \text{if }\bar d\ge11.\]
Code: constants.py
Numerically, \(\frac{48}7=6.857\ldots\), so part (2) reads \(r^{m/6.857+o(m)}\), and \(\frac{3F_4}{2+16F_4}<0.12429\). For cubic constraint graphs (\(m=\frac32n\)), part (3) reads \(r^{(2c_{3}/3)m+o(m)}\) with \(\frac{2c_{3}}3<0.09322\).
Proof. In each part we compute a path decomposition of the constraint graph and run Lemma 11.1(a) with \(D_v=[r]\); its running time and space are \(r^{w+1}\mathop{\mathrm{poly}}(n)\) for a decomposition of width \(w\), so it suffices to bound \(w\). Isolated vertices of \(G\) are handled separately in time \(O(rn)\) (each contributes a factor \(\bigoplus_as_v(a)\)), so we may assume that \(G\) has none; then \(n\le2|E(G)|\le 2m\).
(1) Apply reduction operations to \(G\) until none applies, and let \(R\) be the final graph. By Theorem 1.3 and Theorem 1.5 applied to \(R\), we compute a decomposition of \(R\) of width at most \(\beta(R)+\rho(|V(R)|)\), and by Lemma A.28 with no deletions one of \(G\) of width at most \(\beta(R)+\rho(|V(R)|)+3\log_2n+1=\beta(R)+o(n)\), since \(\rho\) is nondecreasing (Theorem 10.1). Reduction operations only remove vertices and do not increase degrees by (RP1), and \(0\le a_d\le a_{d+1}\) for all \(d\ge0\) (with \(a_0=a_1=a_2=0\)); hence \(\beta(R)\le\beta(G)\).
(2) By Theorem 10.1 (general case), \(w\le\frac7{48}|E(G)|+ \rho(2|E(G)|)\le\frac7{48}m+o(m)\).
(3) If \(\Delta(G)\le3\), Lemma 11.2 gives \(w\le c_{3} n_3(G)+o(n)\). If \(\Delta(G)\le4\), Theorem 7.1 and Theorem 1.5 give \(w\le\beta_4(G)+o(n)\), by running the algorithm for each of the three forms and keeping the narrowest decomposition. For the bound in \(m\), let \(R\) be the final graph of a maximal sequence of reduction operations applied to \(G\); it is empty or has \(\delta(R)\ge3\), and \(\Delta(R)\le4\). If \(R\) is empty, \(w=O(\log n)=o(m)\) by Lemma A.28 with no deletions. Otherwise put \(n':=|V(R)|\), \(m':=|E(R)|\) and \(x:=n_4(R)/n'\in[0,1]\). Then \(n_3(R)=(1-x)n'\) and \(2m'=3n_3(R)+4n_4(R)=(3+x)n'\), so \[\frac{F_4n'}{m'}=\frac{2F_4}{3+x},\qquad \frac{\frac5{32}n_3(R)+\frac14n_4(R)}{m'}=\frac{5+3x}{16(3+x)} .\] The first ratio decreases in \(x\), and the second increases, since \(\frac{d}{dx}\frac{5+3x}{3+x}=\frac4{(3+x)^2}>0\). Hence the minimum of the two is at most their common value at the crossing point \(x^*=\frac{32F_4-5}3\in(0,1)\), which is \(\frac{2F_4}{3+x^*}=\frac{3F_4}{2+16F_4}\). This expression increases in \(F_4\), and \(F_4<0.24577198\) gives \(\frac{3F_4}{2+16F_4}<0.12429\) (at the crossing, \(x^*\approx0.9549\)). So Theorem 7.1(a),(c) and Theorem 1.5 applied to \(R\) give a decomposition of \(R\) of width at most \(\frac{3F_4}{2+16F_4}m'+\rho(n')\), where \(n'\le\frac23m'\) and \(m'\le|E(G)|\le m\), because reduction operations do not increase the number of edges. By Lemma A.28 with no deletions, \(w\le\frac{3F_4}{2+16F_4}m+o(m)+3\log_2(2m)+1\), which is \(\frac{3F_4}{2+16F_4}m+o(m)\).
(4) Part (1) gives the running time \(O^{*}(r^{\beta(G)+o(n)})\) for the given instance. By Corollary 9.15, applied to the constraint graph \(G\) with all its \(n\) vertices (isolated ones included), \(\beta(G)=\sum_{d\ge3}a_dn_d\le n\,A(\bar d)\), where \(A(\bar d)\le1-\frac{111}{28(\bar d+1)}\) if \(\bar d\ge7\) and \(A(\bar d)\le1-\frac4{\bar d+1}\) if \(\bar d\ge11\). ∎
This improves the previous records in sparse instances. Other methods solve dense instances faster. For integer scores of polynomial size, Williams’s algorithm (Williams 2005) runs in time \(O^{*}(r^{\omega n/3})\), where \(\omega\) is the matrix multiplication exponent (domain \(r\): (Scott and Sorkin 2009 Thm. 18)). With \(\omega\le\frac94\) (OpenAI 2026), which Pass proves with integer arithmetic (Pass 2026 Theorem 1.1), as Williams’s algorithm needs, this algorithm is faster than ours when \(\bar d>15\). For very large \(\bar d\), an algorithm of Golovnev and Kutzkov has a smaller exponent (Edwards and McDermid 2015, 942): for Boolean domains it runs in polynomial space and time \(O^{*}\bigl(2^{(1-\alpha\ln\bar d/\bar d)n}\bigr)\) for every constant \(\alpha\in(0,1)\) and every sufficiently large \(\bar d=o(n)\) (Golovnev and Kutzkov 2014 Thm. 4). Their threshold on \(\bar d\) is not explicit, so we do not determine that crossover. Hence part (4) is a record only for moderate \(\bar d\), and for integer scores of polynomial size only for \(\bar d\le15\).
11.4 Domination, independent sets and vertex covers in graphs of bounded degree
This subsection runs dynamic programs for domination, independent sets and five further local problems over the decompositions of Lemma 11.2 (for \(\Delta\le3\)) and Theorem 7.1 (for \(\Delta\le4\)), and an algorithm for Odd Cycle Transversal over the orderings of Theorem 3.6. We use the dynamic programs of Lemma 11.1(b),(c) and five previous algorithms. Most previous bounds come from the same dynamic programs over decompositions of width \(\frac n6\) for \(\Delta\le3\) (Fomin and Høie 2006) and \(\frac n3\) for \(\Delta\le4\) (Fomin et al. 2009), which the new widths \(c_{3}n_3+o(n)\le c_{3}n+o(n)\) and \(\beta_4(G)+o(n)\le F_4n+o(n)\) replace. For instance, the dominating sets of each size of a graph with \(\Delta\le3\) are counted in time \(O(1.1661^n)\) instead of \(3^{n/6}<1.2010^n\).
Theorem 11.4 (bounded-degree graph problems). Let \(G\) be a graph with \(n\) vertices.
(a) If \(\Delta(G)\le3\), then in time and space \(O^{*}(3^{c_{3}n_3+o(n)})=O(1.1661^n)\) one can count the dominating sets of \(G\) of each size, find a minimum weight dominating set and count the dominating sets of minimum weight.
(b) A maximum weight independent set of \(G\) can be found, and the maximum weight independent sets counted, in time and space \(O^{*}(2^{c_{3}n_3+o(n)})=O(1.1018^n)\) if \(\Delta(G)\le3\), and \(O^{*}(2^{\beta_4(G)+o(n)})=O(1.1858^n)\) if \(\Delta(G)\le4\).
(c) If \(\Delta(G)\le3\), then, in time and space \(O^{*}(2^{c_{3}n_3+o(n)})=O(1.1018^n)\), one can find \(k\) vertices that cover the most edges (Max \(k\)-Vertex Cover); in time and space \(O^{*}(3^{c_{3}n_3+o(n)})=O(1.1661^n)\), a minimum independent dominating set; and in time and space \(O^{*}(6^{c_{3}n_3+o(n)})=O(1.2848^n)\), a minimal dominating set of maximum size (Upper Domination). If \(\Delta(G)\le4\), a minimum independent dominating set can be found in time and space \(O^{*}(3^{\beta_4(G)+o(n)})=O(1.3100^n)\).
(d) If \(\Delta(G)\le3\), a minimum edge dominating set and a minimum maximal matching of \(G\) can be found in time and space \(O^{*}(3^{c_{3}n_3+o(n)})=O(1.1661^n)\).
(e) A minimum odd cycle transversal of \(G\) can be found by a deterministic algorithm in time \(O^{*}(2^{m/6+o(n)})=O(1.2600^n)\) if \(\Delta(G)\le4\) and in time \(O^{*}(2^{\gamma_5m+o(n)})=O(1.4262^n)\) if \(\Delta(G)\le5\), where \(m=|E(G)|\) and \(\gamma_5<0.20484\) is the constant of Theorem 3.6.
Proof. If \(\Delta(G)\le3\), Lemma 11.2 gives a path decomposition of width at most \(c_{3}n_3+o(n)\) in polynomial time; if \(\Delta(G)\le4\), Theorem 7.1 and Theorem 1.5 give one of width at most \(\beta_4(G)+o(n)\). Run Lemma 11.1(b) for (a) and Lemma 11.1(c) for (b). For (c) we run, on these decompositions, the dynamic program for Max \(k\)-Vertex Cover in time \(O^{*}(2^{\mathop{\mathrm{pw}}})\) and exponential space that Della Croce and Paschos combine with the bound of Fomin and Høie (Croce and Paschos 2012 Corollary 2), the dynamic program for Independent Dominating Set in time \(O(n^33^{\mathop{\mathrm{tw}}})\) of van Rooij (Rooij 2011 Proposition 11.11), and that for Upper Domination in time \(O(6^{\mathop{\mathrm{pw}}}\mathop{\mathrm{pw}})\) of Dublois, Lampis and Paschos (Dublois, Lampis, and Paschos 2022 Theorem 10). For (d) we run the dynamic program of van Rooij and Bodlaender, which finds a minimum weight maximal matching in time \(O^{*}(3^{\mathop{\mathrm{pw}}})\) on a path decomposition of width \(\mathop{\mathrm{pw}}\) (Rooij and Bodlaender 2012 Lemma 3). A minimum maximal matching is an edge dominating set, and a minimum edge dominating set can be turned in polynomial time into a maximal matching of the same size (Yannakakis and Gavril 1980). For (e), Theorem 10.3 computes, in deterministic polynomial time, an ordering of cutwidth at most \(\frac m6+o(n)\le\frac n3+o(n)\) or \(\gamma_5m+o(n)\le\frac52\gamma_5n+o(n)\), and Bojikian, Chekan, Hegerfeld and Kratsch find a minimum odd cycle transversal deterministically in time \(2^{\operatorname{ctw}}n^{O(1)}\) for a given ordering of cutwidth \(\operatorname{ctw}\) (Bojikian et al. 2022 Theorem 36), with \(2^{1/3}<1.25993\) and \(2^{5\gamma_5/2}<1.42611\), where \(\gamma_5=\frac1\pi\arccos\frac45\). The numerical bases follow from \(n_3\le n\), \(F_4n\) being one of the three forms, \(3^{c_{3}}<1.16604\), \(2^{c_{3}}<1.10177\), \(6^{c_{3}}<1.28471\), \(2^{F_4}<1.18573\) and \(3^{F_4}<1.30998\). ∎
11.5 Counting subgraphs
Curticapean, Dell and Marx reduce counting the subgraphs of a host graph that are isomorphic to a pattern to counting homomorphisms from the graphs of the spasm of the pattern (defined below), and the treewidth of these graphs governs the running time. For a pattern with \(k\) edges, their bound \(k^{O(k)}n^{0.174k+o(k)}\) comes from the Scott–Sorkin bound \(\frac{13}{75}k+o(k)\) on the treewidth of graphs with \(k\) edges; Remark 9.14 lowers the exponent to \(\frac7{48}k+o(k)\) (Theorem 11.5).
For a graph \(H\), the spasm of \(H\) is the set of graphs \(H/\pi\) obtained from \(H\) by choosing a partition \(\pi\) of \(V(H)\) into independent sets and identifying the vertices of each part, keeping one copy of parallel edges (Curticapean, Dell, and Marx 2017). Since every part is independent, \(H/\pi\) is simple without loops, and every edge of \(H/\pi\) is the image of an edge of \(H\), so \(|E(H/\pi)|\le|E(H)|\).
Theorem 11.5 (counting subgraphs). There is a function \(\rho(k)=o(k)\) such that, given a pattern graph \(H\) with \(k\) edges and a host graph \(G\) with \(n\) vertices, the number of subgraphs of \(G\) isomorphic to \(H\) can be computed in time \(k^{O(k)}\,n^{\frac7{48}k+\rho(k)}\).
In particular this holds for counting paths, cycles and matchings with \(k\) edges. Numerically, \(\frac7{48}<0.14584\).
Proof. By (Curticapean, Dell, and Marx 2017 Thm. 1.1), the number of subgraphs of \(G\) isomorphic to \(H\) can be computed in time \(k^{O(k)} n^{t+1}\), where \(t\) is the largest treewidth of a graph in the spasm of \(H\). Every graph \(F\) in the spasm is simple and has at most \(k\) edges. By Remark 9.14, \(\mathop{\mathrm{tw}}(F)\le\mathop{\mathrm{pw}}(F)\le\frac7{48}|E(F)|+\rho(|E(F)|+1)\), where \(\rho\) is the nondecreasing remainder of Remark 9.14; so \(t\le\frac7{48}k+\rho(k+1)\), and the theorem holds with the function \(k\mapsto\rho(k+1)+1\) in place of \(\rho\). (The algorithm needs tree decompositions of the graphs of the spasm; they can be computed by brute force in time depending on \(k\) only, or by Theorem 1.5.) ∎
11.6 Bucketing: permutation patterns and \(k\)-opt
This subsection lowers two exponents of the form \(\frac k4\) to \(\frac{253}{1215}k+o(k)\) (note that \(\frac{253}{1215}<0.2083\)): for Permutation Pattern Matching with a pattern of length \(k\), from the bound \(n^{k/4}\) of Berendsohn, Kozma and Marx (Berendsohn, Kozma, and Marx 2021), and for \(k\)-opt Optimization for TSP, from the bound \(n^{(1/4+\varepsilon_k)k}\), with \(\varepsilon_k\to0\), of Cygan, Kowalik and Socała (Cygan, Kowalik, and Socała 2019). On graphs of bounded degree, Remark 9.14 also lowers the exponent \((\frac{23}{135} +\varepsilon_k)k\) of \(k\)-opt Optimization (Bonnet et al. 2019) to \((\frac7{48}+\varepsilon_k)k\) (Theorem 11.8). We first define the two problems.
In Permutation Pattern Matching the input is a pattern \(\pi\colon[k]\to[k]\) and a text \(\tau\colon[n]\to[n]\), both permutations, with \(k\le n\). An occurrence of \(\pi\) in \(\tau\) is a strictly increasing map \(f\colon[k]\to[n]\) such that \(\tau(f(i))<\tau(f(j))\) if and only if \(\pi(i)<\pi(j)\); the decision version asks whether an occurrence exists, and the counting version for their number. In \(k\)-opt Optimization for TSP the input is an edge-weighted graph with a Hamiltonian cycle, and the task is to find a \(k\)-opt move (removing \(k\) edges of the cycle and adding \(k\) edges so as to obtain a Hamiltonian cycle) of maximum gain (Cygan, Kowalik, and Socała 2019; Bonnet et al. 2019).
Cygan, Kowalik and Socała (Cygan, Kowalik, and Socała 2019) introduced a bucketing argument for \(k\)-opt, and Berendsohn, Kozma and Marx (Berendsohn, Kozma, and Marx 2021) transferred it to Permutation Pattern Matching. It trades the number of guesses against the pathwidth of a graph made of a cycle cover (or a path) and some edges of the path \(1,2,\dots,k\): coarser buckets mean fewer guesses but larger domains. Both previous bounds \(n^{k/4}\) come from a coefficient \(\frac13\) for graphs of maximum degree \(4\). A single smaller coefficient for maximum degree \(4\), such as \(F_4\), improves the bound obtained without bucketing to \(n^{F_4k}\), but it does not combine with bucketing to anything better: inside the trade-off, the pathwidth bound has to grow with the number of path edges. The per-degree bounds of Theorem 7.1(b),(c) and Theorem 7.2 have exactly this property. We use the triple \(\mathsf{R}\) of Theorem 7.2, with \(n_5=0\); within our argument, adding the bounds of Theorems 7.1 and 8.2 does not lower the exponent further (see Appendix A.7.2). We first bound the pathwidth of the graphs that arise (Lemma 11.6), then solve the trade-off (Lemma 11.7), and finally apply both lemmas to the two problems (Theorem 11.8).
For an integer \(k\ge1\) and a real \(s\in[0,k]\) put \[p(s):=\min\bigl\{0.291\,s,\ 0.038\,k+0.215\,s\bigr\};\] \(k\) is fixed wherever \(p\) is used. We write \(P_k:=\{\{i,i+1\}:i\in[k-1]\}\) for the edge set of the path \(1,2,\dots,k\).
Lemma 11.6 (cycle cover plus path edges). There is a function \(\rho(k)=o(k)\) such that the following holds. Let \(C\) be a multigraph on \([k]\), possibly with loops, of maximum degree at most \(2\), and let \(A\subseteq P_k\) with \(|A|=s\). Then the simple graph \(H\) underlying \(C\cup A\) satisfies \(\mathop{\mathrm{pw}}(H)\le p(s)+\rho(k)\), and a path decomposition of \(H\) of this width can be computed in polynomial time.
The bucketing exponent is a maximum over \(s\) of a weighted sum of the number \(k-s\) of guessed buckets and the width bound \(p(s)\); the weight \(\alpha\) is the exponent of the bucket width. The next lemma chooses \(\alpha\).
Lemma 11.7 (the trade-off). Let \(\alpha=\frac{200}{243}\). For every \(0\le s\le k\), \[(1-\alpha)(k-s)+\alpha\,p(s)\le\tfrac{253}{1215}k .\] Moreover, no \(\alpha\in[0,1]\) gives a smaller bound than \(\frac{253}{1215}k\) on \(\max_{0\le s\le k}[(1-\alpha)(k-s)+\alpha p(s)]\).
The proofs of the two lemmas, and a check that the other bounds of Part I do not lower the exponent within this argument, are in Appendix A.7.2.
The two lemmas give the following bounds for the problems defined at the start of this subsection.
Theorem 11.8 (permutation patterns and \(k\)-opt). There are a function \(\rho(k)=o(k)\) and numbers \(\varepsilon_k\to0\) such that:
(a) the decision and counting versions of Permutation Pattern Matching, for a pattern of length \(k\) and a text of length \(n\), can be solved in time \(2^{O(k)}\,n^{\frac{253}{1215}k+\rho(k)}\);
(b) for every fixed \(k\), \(k\)-opt Optimization can be solved in time \(O(n^{(253/1215+\varepsilon_k)k})\) on \(n\)-vertex edge-weighted graphs, and in time \(O(n^{(7/48+\varepsilon_k)k})\) on those of bounded maximum degree.
The proof, in Appendix A.7.2, follows Berendsohn, Kozma and Marx for (a) and Cygan, Kowalik and Socała for (b), with Lemmas 11.6 and 11.7 in place of their pathwidth bounds, and with Remark 9.14 for bounded degree.