Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential Algorithms
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 c3 n+o(n), where c3=3/4πarccos5/6≈0.1398. For bisection width this improves the bound n/6+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 n/3+o(n), improving the bound 2n/5+o(n) of Monien and Preis for 4-regular graphs, and that pathwidth is at most 0.2458n, improving the bound n/3 of Fomin, Gaspers, Saurabh and Stepanov (2009). We show that every graph with m edges has pathwidth at most 7m/48+o(n), improving the bound 13m/75 of Scott and Sorkin (2007), and we give further bounds of the form ∑d≥3ad nd+o(n) with ad<1, where nd 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 over a ball around it, and sweep a threshold through the labels; the bags are frontiers, the vertices above the threshold with a neighbor below it. We bound the probability that a vertex lies in a frontier by comparison with an explicit Gaussian model of a vertex and its neighbors. Faster exact algorithms follow: for feedback vertex set and the traveling salesperson problem on graphs of bounded maximum or average degree, and on general graphs for minimum weight dominating set (by branching until the instance is sparse), Max 2-CSP and counting subgraphs with k edges (by the bound in m).
Related
- Optimal path decompositions of sparse random graphs
- Quantitative non-Gaussian and Gaussian approximation for exponential random graphs in the single-phase critical regime
- Majority Dynamics on Resampled Sparse Erdős--Rényi Graphs: Gaussian Winner Selection in Collaborative Agent Networks
- An improved minimum degree threshold for fractional clique decompositions in partite graphs
- A note on decompositions into 3-chromatic graphs
BibTeX
@misc{gaspers2026path,
title = {{Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential Algorithms}},
author = {Serge Gaspers},
howpublished = {arXiv},
year = {2026},
month = nov,
doi = {10.48550/arxiv.2611.05146},
eprint = {2611.05146},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2611.05146},
}
RIS
TY - UNPB
TI - Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential Algorithms
AU - Serge Gaspers
PY - 2026
DA - 2026/11/03
PB - arXiv
DO - 10.48550/arxiv.2611.05146
UR - https://arxiv.org/abs/2611.05146
AB - 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=3/4πarccos5/6≈0.1398. For bisection width this improves the bound n/6+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 n/3+o(n), improving the bound 2n/5+o(n) of Monien and Preis for 4-regular graphs, and that pathwidth is at most 0.2458n, improving the bound n/3 of Fomin, Gaspers, Saurabh and Stepanov (2009). We show that every graph with m edges has pathwidth at most 7m/48+o(n), improving the bound 13m/75 of Scott and Sorkin (2007), and we give further bounds of the form ∑_d≥3a_d n_d+o(n) with 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 over a ball around it, and sweep a threshold through the labels; the bags are frontiers, the vertices above the threshold with a neighbor below it. We bound the probability that a vertex lies in a frontier by comparison with an explicit Gaussian model of a vertex and its neighbors. Faster exact algorithms follow: for feedback vertex set and the traveling salesperson problem on graphs of bounded maximum or average degree, and on general graphs for minimum weight dominating set (by branching until the instance is sparse), Max 2-CSP and counting subgraphs with k edges (by the bound in m).
ER -