10 Computing the decompositions

This section turns the width bounds of Theorems 8.1, 7.1, 7.2 and 1.3 and Corollary 1.4, and with Appendix A.6 also those of Theorems 8.2 and 9.2 and Corollary 9.5, into algorithms that compute the decompositions. The proofs of these bounds are probabilistic. The frontiers of a random Gaussian labeling have the right expected size at every threshold and concentrate around it, and Lemma 4.1, or the median-switched layout of Lemma 8.4, turns a good labeling into a path decomposition. We state Theorem 10.1, the precise form of Theorem 1.5, which gives a Las Vegas and a deterministic algorithm for each of these bounds, and outline its proof, which is in Appendix A.5. Part II uses this theorem, mostly its deterministic part, whenever an algorithm needs a decomposition of the width given by Part I.

10.1 Statement and outline

Model.

The input graph \(G\) has vertices \(1,\dots,n\) and is given by adjacency lists. Running times count bit operations on integers and rationals in binary; in the bootstrap and general cases below we also count operations on integers of \(O(\log n)\) bits, which serve as vertex names and indices. The Las Vegas algorithms have access to independent uniform random bits. A path decomposition \((W_1,\dots,W_s)\) is output in interval form (Section 4.1), that is, as the number \(s\) and, for each vertex \(v\), the indices \(\mathrm{first}(v)\le \mathrm{last}(v)\) of the first and the last bag containing \(v\). This takes \(O(n\log n)\) bits when \(s=O(n)\), as for all our decompositions. The bags themselves can have total size of order \(n^2\), so the running times below refer to the interval form. The terms \(o(1)\) in the exponents of running times are functions of \(n\) alone.

Cases.

Each case of the following theorem consists of a class \(\mathcal C\) of graphs, given by a condition on \(G\), and a bound \(\beta(G)\) for \(G\in\mathcal C\):

• cubic case: \(\Delta(G)\le3\) and \(\beta(G)=c_{3}n\);

• padded case: \(\Delta(G)\le4\) and \(\beta(G)=F_4n\);

• switched case: \(\Delta(G)\le4\) and \(\beta(G)=c_{3}n_3+0.2627\,n_4\);

• mixed cases: \(\Delta(G)\le5\) and \(\beta(G)=a_3n_3+a_4n_4+a_5n_5\) with \((a_3,a_4,a_5)\in\{\mathsf{P},\mathsf{R},\mathsf{S}\}\);

• bootstrap cases: all graphs, and \(\beta(G)=\sum_{d\ge3}b_dn_d\), where \((b_d)_{d\ge3}\) is the bootstrap of one of the six sequences \(\mathsf{C},\mathsf{M},\mathsf{F},\mathsf{P},\mathsf{R},\mathsf{S}\) of Theorem 9.2;

• general case: all graphs, and \(\beta(G)=\sum_{d\ge3}a_dn_d\) with the coefficients \(a_d\) of Theorem 1.3.

Theorem 10.1 (precise form of Theorem 1.5).  In each case listed above there are a nondecreasing function \(\rho\colon\mathbb{N}\to[0,\infty)\) with \(\rho(n)=o(n)\) and two algorithms that, given \(G\in\mathcal C\), output a path decomposition of \(G\) in interval form, of width at most \(\beta(G)+\rho(n)\), and in the general case also at most \(\frac7{48}m+\rho(2m)\):

(a)  a Las Vegas algorithm, in expected \(n^{1+o(1)}\) bit operations;

(b)  a deterministic algorithm, in \(n^{2+o(1)}\) bit operations.

In the bootstrap and general cases, each algorithm uses in addition \(O(n(n+m))\) operations on integers of \(O(\log n)\) bits.

Lean proof for a port of the implementation (the outputs, not the running times): Alg.algoT1Valid, Alg.algoT2aValid, Alg.algoMixedValid, Alg.algoT4Valid, Alg.algoT1NoFallback, Alg.algoMixedNoFallback, Alg.algoT4NoFallback, Alg.algoT1Width, Alg.algoT2aWidth, Alg.algoMixedWidth, Alg.algoT4Width, Alg.algoT1RealizesTheorem1, Alg.algoT2aRealizesTheorem2a, Alg.algoMixedRealizesTheorem2b, Alg.algoMixedRealizesTheorem2c, Alg.algoMixedRealizesTheorem3P, Alg.algoMixedRealizesTheorem3R, Alg.algoMixedRealizesTheorem3S, Alg.algoT4RealizesTheorem4, Alg.algoT4RealizesCorollary5 (what is formalised)

Here \(\rho\) is the remainder of the width bound. The bounds \(\beta\) are those of Theorem 8.1, Theorem 7.1(a), Theorem 8.2, Theorem 7.2, Lemma 9.3 and Theorem 1.3 without their remainders, and the second bound of the general case is that of Corollary 1.4. A graph with \(\Delta(G)\le4\) has \(n_5=0\), so the mixed cases with \(\mathsf{P}\) and \(\mathsf{S}\) also give the bounds of Theorem 7.1(b) and (c). The bootstrap cases give the rows of Corollary 9.5 and the sequences of Theorem 9.2 on all graphs (Remark A.35); the general case is the bootstrap case of \(\mathsf{S}\) in the rounded form of Theorem 1.3. Theorem 1.5 follows from Theorem 10.1.

Outline.

The proof of each case follows the same pattern. The algorithm computes discrete labels \(\tilde Y_v\), sorts the vertices by \((\tilde Y_v,v)\), and builds the layout of the case from the sorted order. The width of that layout is bounded by a finite family of counts, each the number of vertices satisfying a condition on the labels in their closed neighborhood (Lemma A.31 and Appendix A.5.8). Four ingredients, shared by all cases, bound the counts.

(1)  Exact local labels (Appendices A.5.1 and A.5.2). We round the coefficients of Definition 5.2 to rationals, and we replace the Gaussian variables by a finite rational distribution coupled with the standard normal distribution (Lemma A.23).

(2)  Perturbation (Appendix A.5.3). In this coupling every per-vertex probability used in Part I changes by \(o(1)\), uniformly in the threshold (Lemma A.24 and Corollary A.25).

(3)  Uniform ideal means (Appendix A.5.4). The grid of thresholds refines as \(n\) grows, so the bounds on expected frontier sizes are needed uniformly in the threshold (Lemma A.26). In the cubic, padded and mixed cases the bounds of Part I already have this form, with an error term \(O(1/h)\); in the switched case, Lemma A.37 makes the error term at threshold zero explicit, as \(O(\varepsilon_h^{1/3})\).

(4)  Derandomization (Appendix A.5.5). The counts are close to their means with high probability. The method of conditional expectations (Erdős and Selfridge (Erdős and Selfridge 1973); Raghavan (Raghavan 1988)), applied to the sum of the squared deviations of the counts, fixes the random variables one at a time so that every count is close to its mean (Lemma A.27). The locality radius grows only like \(\frac18\log_2\log_2n\), so every conditional expectation is a sum of local terms, each computable exactly in \(n^{o(1)}\) bit operations.

Derandomizing a local Gaussian rounding in this way is standard in outline; the work lies in the exact finite distribution and in the uniformity of the means.

Roadmap.

The proof is in Appendix A.5. Appendices A.5.1, A.5.2, A.5.3, A.5.4 and A.5.5 develop the four ingredients in this order, and Appendix A.5.6 makes the construction of Lemma 4.5 algorithmic. Appendices A.5.7, A.5.8 and A.5.9 assemble the algorithms for the padded and mixed cases, the cubic case, and the bootstrap and general cases, Appendix A.6 treats the switched case and the base layouts of the bootstrap cases \(\mathsf{C}\) and \(\mathsf{M}\), and Appendix A.5.10 collects the running times. The rest of this section computes orderings of small cutwidth for maximum degree \(3\), \(4\) and \(5\) and discusses the limitations.

10.2 Linear orderings of small cutwidth

This subsection computes, for graphs of maximum degree \(3\), linear orderings of cutwidth at most \(c_{3}n+o(n)\), and bisections with at most that many edges between the two sides (Corollary 10.2). Corollary 1.2 shows that such orderings and bisections exist, by bounding the cutwidth through a chain of known relations. Two links of that chain have constructive proofs, which turn an ordering of vertex separation \(w\), such as the one read off a path decomposition of Theorem 10.1, into an ordering of cutwidth at most \(w+2\) (Lemma A.36, proved in Appendix A.5.11). For maximum degree \(4\) and \(5\), Theorem 10.3 derandomizes the cut sweep of Theorem 3.6 directly, with the machinery of Appendices A.5.1, A.5.2, A.5.3 and A.5.5. The two routes differ because they start from different bounds. For maximum degree \(3\) the cut sweep gives only \(\gamma_3m\le c_*n\), while the route through vertex separation gives \(c_{3}n<c_*n\). For maximum degree \(4\) the same chain gives only \(\operatorname{cw}\le2\mathop{\mathrm{pw}}+O(1)\) (Makedon and Sudborough 1989 Theorem 3.2; Ellis, Sudborough, and Turner 1994 Theorem 2.1), that is, \(2F_4n+o(n)>\frac n3\).

Corollary 10.2 (computing orderings and bisections).  For graphs \(G\) with \(\Delta(G)\le3\), an ordering of \(V(G)\) of cutwidth at most \(c_{3}n+o(n)\), and a bisection of \(G\) with at most \(c_{3}n+o(n)\) edges between its two sides, can be computed in deterministic time \(n^{2+o(1)}\).

The proof is in Appendix A.5.11.

Theorem 10.3 (deterministic cut sweep).  Let \(p\in\{4,5\}\). For graphs \(G\) with \(\Delta(G)\le p\) and \(m\) edges, an ordering of \(V(G)\) of cutwidth at most \(\gamma_pm+o(n)\), and a bisection of \(G\) with at most that many edges between its two sides, can be computed in deterministic time \(n^{2+o(1)}\). For \(p=4\) the bound is \(\frac m6+o(n)\le\frac n3+o(n)\).

The proof is also in Appendix A.5.11.

10.3 Limitations

The guarantees of Theorem 10.1 are asymptotic: our analysis assumes \(n\ge2^{2^{40}}\), and some error terms are below \(1\) only when \(\log_2\log_2n\) exceeds \(10^4\) or even \(10^5\), so the bounds say nothing for practical \(n\). The terms \(o(1)\) in the exponents also hide enumeration factors \(e^{O(t^{1/4}\log t)}\) with \(t=O(\log n)\), and practical efficiency is not claimed.

Part II derives faster exact algorithms from the width bounds of Part I. Before the proofs, which begin in Section 11, this opening gathers the new running-time bounds and says which of them the two recent preprints that claim to refute the ETH (OpenAI 2026; Claude 2026) (Section 1.2) would supersede.

The tables.

Table 2 lists the running-time bounds of this part in exponential space that, as far as we know, the preprints do not affect, and Table 5 lists those in exponential space that the preprints would supersede. Both tables follow the conventions stated after Theorem 1.6. “Previous” is the fastest bound that we are aware of.

Bounds in polynomial space.

Neither table lists bounds in polynomial space; we state them here. Separate, Measure and Conquer with the separator constant \(c_{3}\) (Theorem C.3) solves Max \((r,2)\)-CSP in polynomial space in time \(r^{0.17587m+o(m)}\), in time \(r^{0.16984m+o(m)}\) if \(\Delta\le4\) and in time \(r^{0.17935n+o(n)}\) on cubic instances. The previous bounds are \(r^{9m/50}\), \(r^{7m/40}\) and \(r^{n/5}\) up to subexponential factors (Gaspers and Sorkin 2017 Theorems 3.1–3.3). As far as we know, the preprints do not affect these three bounds for Max \((r,2)\)-CSP. The same method counts the dominating sets of each size of a graph with \(\Delta\le3\) in polynomial space and time \(O(1.2178^n)\), against \(O(1.2458^n)\) (Gaspers and Sorkin 2017 Theorem 5.1).

By Theorem C.6, proved in Appendix C, the independent sets of a graph can be counted in polynomial space in time \(O(1.1304^n)\) if \(\Delta\le3\), \(O(1.2037^n)\) if \(\Delta\le4\) and \(O(1.2341^n)\) in general, and its chromatic number can be computed in polynomial space in time \(O(2.2341^n)\). The previous bounds, of Gaspers and Lee (Gaspers and Lee 2023 Lemmas 5 and 6, Theorem 1), are \(O(1.1389^n)\), \(O(1.2070^n)\), \(O(1.2356^n)\) and \(O(2.2356^n)\). The previous analysis of the bound \(O(1.1389^n)\) has open points (Appendix C); our bound \(O(1.1304^n)\) includes the necessary corrections.

The reach of the preprints.

The preprints reach other problems through the subexponential reduction families of Impagliazzo, Paturi and Zane (Impagliazzo, Paturi, and Zane 2001), which make every problem in size-constrained SNP solvable in subexponential time if #3-SAT is, and through direct counting algorithms (Claude 2026 Corollary 7), (OpenAI 2026 Corollary 1.3). If correct, they supersede seventeen of our bounds: the twelve of Table 5 and the five in polynomial space above. For the chromatic number this uses inclusion–exclusion (Björklund, Husfeldt, and Koivisto 2009); for Max 2-SAT, Max \(k\)-Vertex Cover, Upper Domination, Edge Dominating Set and Odd Cycle Transversal on graphs of bounded degree, an encoding in size-constrained SNP or in \(k\)-SAT with \(O(n)\) variables; for Independent Dominating Set, a result of Ganian, de Haan, Kanj and Szeider (Ganian et al. 2016 Corollary 6). As far as we know, the problems of Table 2 lie outside this reach: they have real weights, a global connectivity or acyclicity constraint (whether Feedback Vertex Set is SERF-reducible to 3-SAT is open (Ganian et al. 2016)), or running times \(n^{ck}\) in a pattern size \(k\), and we know of no SERF reduction from any of them to 3-SAT or #3-SAT.

Table 5: The running-time bounds of this part in exponential space that would be superseded if the preprints (OpenAI 2026; Claude 2026) that claim to refute ETH are correct. Letters refer to the notes; the letters a–h have the same meaning as in Table 2, and the notes i and j are local to this table.

Problem	Previous	New	Where
Max 2-SAT, counting dominating sets and independent sets
Max 2-SAT	$2^{m/6.321}$	$2^{m/6.857}$	Theorem 11.3
#Dominating Set, all graphs	$1.5002^n$ a	$1.4815^n$	Theorem 13.1
#Dominating Set (every size), $\mathrm{\Delta }\le 3$	$3${n/6}<1.2010n	$3${c_{3}n}<1.1661n	Theorem 11.4
#Independent Sets, $\mathrm{\Delta }\le 3$	$2${n/6}<1.1225n	$2${c_{3}n}<1.1018n	Theorem 11.4
#Independent Sets, all graphs	$1.2330^n$	$1.2287^n$	Theorem C.6
Local problems on graphs of bounded degree (deterministic)
Max $k$-Vertex Cover, $\mathrm{\Delta }\le 3$	$1.123^n$	$2${c_{3}n}<1.1018n	Theorem 11.4
Min. Independent Dominating Set, $\mathrm{\Delta }\le 3$	$1.3351^n$ i	$3${c_{3}n}<1.1661n	Theorem 11.4
Min. Independent Dominating Set, $\mathrm{\Delta }\le 4$	$1.3351^n$ i	$3${F_4n}<1.3100n	Theorem 11.4
Upper Domination, $\mathrm{\Delta }\le 3$	$1.3481^n$	$6${c_{3}n}<1.2848n	Theorem 11.4
Edge Dominating Setj, $\mathrm{\Delta }\le 3$	$3${n/6}<1.2010n	$3${c_{3}n}<1.1661n	Theorem 11.4
Odd Cycle Transversal, $\mathrm{\Delta }\le 4$	$3${n/3}<1.4423n	$2${n/3}<1.2600n	Theorem 11.4
Odd Cycle Transversal, $\mathrm{\Delta }\le 5$	$3${13n/30}<1.6098n	$2${0.5121n}<1.4262n	Theorem 11.4

^a A gap in the analysis of this algorithm allowed us only to reconstruct a running time of \(O(1.5004^n)\) (Appendix D.5). ⁱ A bound for all graphs. ^j Also Minimum Maximal Matching.

Conventions for Part II.

We write \(O^{*}(f)\) for \(f\cdot\mathop{\mathrm{poly}}(N)\), where \(N\) is the length of the input. All remainders \(o(n)\), \(o(m)\) and \(o(k)\) are functions of the displayed parameter alone. The results of Part II are worst-case asymptotic statements, as are the records they improve. Numerical bases are rounded up in the last printed digit, so that \(c^{n+o(n)}=O(b^n)\) holds for the printed \(b\). Running times of the form \(r^{\alpha n+o(n)}\) are stated with the exact exponent; their numerical values come from the accompanying code. By the previous record for a problem we mean the fastest algorithm we know of.

References

Björklund, Andreas, Thore Husfeldt, and Mikko Koivisto. 2009. “Set Partitioning via Inclusion-Exclusion.” SIAM Journal on Computing 39 (2): 546–63. https://doi.org/10.1137/070683933.

Claude. 2026. “A \(2^{o(n)}\) Time Algorithm for 3-SAT.” Anthropic preprint, dated 26 October 2026, with a Lean 4 formalization, in the folder eth of the repository. https://github.com/anthropics/formal-math.

Ellis, John A., Ivan Hal Sudborough, and Jonathan S. Turner. 1994. “The Vertex Separation and Search Number of a Graph.” Information and Computation 113 (1): 50–79. https://doi.org/10.1006/INCO.1994.1064.

Erdős, Paul, and John L. Selfridge. 1973. “On a Combinatorial Game.” Journal of Combinatorial Theory, Series A 14 (3): 298–301. https://doi.org/10.1016/0097-3165(73)90005-8.

Ganian, Robert, Ronald de Haan, Iyad A. Kanj, and Stefan Szeider. 2016. “On Existential MSO and Its Relation to ETH.” In 41st International Symposium on Mathematical Foundations of Computer Science, MFCS 2016, 58:42:1–14. Leibniz International Proceedings in Informatics (LIPIcs). Schloss Dagstuhl – Leibniz-Zentrum für Informatik. https://doi.org/10.4230/LIPIcs.MFCS.2016.42.

Gaspers, Serge, and Edward J. Lee. 2023. “Faster Graph Coloring in Polynomial Space.” Algorithmica 85 (2): 584–609. https://doi.org/10.1007/S00453-022-01034-7.

Gaspers, Serge, and Gregory B. Sorkin. 2017. “Separate, Measure and Conquer: Faster Polynomial-Space Algorithms for Max 2-CSP and Counting Dominating Sets.” ACM Transactions on Algorithms 13 (4): 44:1–36. https://doi.org/10.1145/3111499.

Impagliazzo, Russell, Ramamohan Paturi, and Francis Zane. 2001. “Which Problems Have Strongly Exponential Complexity?” Journal of Computer and System Sciences 63 (4): 512–30. https://doi.org/10.1006/JCSS.2001.1774.

Makedon, Fillia, and Ivan Hal Sudborough. 1989. “On Minimizing Width in Linear Layouts.” Discrete Applied Mathematics 23 (3): 243–65. https://doi.org/10.1016/0166-218X(89)90016-4.

OpenAI. 2026. “The Exponential Time Hypothesis Is False.” OpenAI Math Release preprint, dated 17 October 2026, revised 25 October 2026, in the folder preprints/The-Exponential-Time-Hypothesis-is-False-October-25-2026 of the repository. https://github.com/openai/math.

Raghavan, Prabhakar. 1988. “Probabilistic Construction of Deterministic Algorithms: Approximating Packing Integer Programs.” Journal of Computer and System Sciences 37 (2): 130–43. https://doi.org/10.1016/0022-0000(88)90003-7.