Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential Algorithms

Author

Serge Gaspers (UNSW Sydney, Australia)

Version. This reading version renders the manuscript of 2 November 2026, the same version as the PDF. Section, statement, equation, table and figure numbers match the PDF. The paper has not yet been submitted or published.

Abstract

Using the bisection bound of Monien and Preis, Fomin and Høie proved in 2006 that every graph of maximum degree \(3\) on \(n\) vertices has pathwidth at most \(n/6+o(n)\). We prove that the pathwidth, bisection width and cutwidth of these graphs are at most \(c_{3}\,n+o(n)\), where \(c_{3}=\frac{3}{4\pi}\arccos\frac56\approx0.1398\). For bisection width this improves the bound \(\frac n6+o(n)\) of Monien and Preis (2006) and extends to all such graphs the bound that Lichev and Mitsche (2023) obtained for random cubic graphs. For maximum degree \(4\), we prove that bisection width and cutwidth are at most \(\frac n3+o(n)\), improving the bound \(\frac{2n}5+o(n)\) of Monien and Preis for \(4\)-regular graphs, and that pathwidth is at most \(0.2458n\), improving the bound \(\frac n3\) of Fomin, Gaspers, Saurabh and Stepanov (2009). We show that every graph with \(m\) edges has pathwidth at most \(\frac{7}{48}m+o(n)\), improving the bound \(\frac{13}{75}m\) of Scott and Sorkin (2007), and we give several further bounds, none best for all graphs, of the form \(\sum_{d\ge3}a_d\,n_d+o(n)\) with coefficients \(a_d<1\), where \(n_d\) is the number of vertices of degree \(d\). The path decompositions, and linear orderings of the stated cutwidth, can be computed in polynomial time.

Instead of deriving pathwidth bounds from bisection width, we give each vertex a Gaussian label, a weighted sum of independent standard normal variables, one for each vertex of a ball around it, so that adjacent vertices have strongly correlated labels. Sweeping a threshold through the labels gives a path decomposition whose bags are frontiers: the vertices above the threshold that have a neighbor below it. We bound the probability that a vertex lies in a frontier from above by comparison with an explicit Gaussian model of a vertex and its neighbors; a refinement of this sweep gives the width \(c_{3}\,n+o(n)\) for maximum degree \(3\).

Faster exact algorithms follow. For graphs of bounded maximum or average degree, they include algorithms for feedback vertex set and the traveling salesperson problem. For general graphs, a branching algorithm that finishes sparse instances by dynamic programming becomes faster for minimum weight dominating set, and the bound in \(m\) gives faster algorithms for Max 2-CSP and for counting subgraphs with \(k\) edges.

Contents

Part I: Width bounds

Part II: Algorithmic consequences

Appendices

How to cite

Serge Gaspers. Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential Algorithms. Manuscript, 2026.

Artifacts

Statements of the paper with a Lean proof or a computer-assisted proof show, below the statement, links to the Lean theorems and to the code. Appendix B describes the formalisation; the formalisation page lists every link in one table, and the code is in ancillary/.

Back to top