CS Paper Radar

A 5/4 bound for graphic $s$-$t$ path TSP on subcubic graphs

Junho Hwang

cs.DS cs.DMmath.CO ·submitted 2026-08-11 15:12 UTC · v2
theory

Abstract

We study the graphic $s$-$t$ path TSP on subcubic graphs (maximum degree 3): given distinct vertices $s,t$, find a shortest $s$-$t$ walk that visits every vertex. We prove an upper bound with the asymptotically optimal leading coefficient $5/4$ for every terminal pair, even when $G-\{s,t\}$ is disconnected. Specifically, every simple 2-connected subcubic graph $G$ on $n$ vertices has a spanning $s$-$t$ walk of length at most $\lfloor(5n+n_2(G))/4\rfloor$, where $n_2(G)$ counts its degree-2 vertices. An $O(n^2)$-time algorithm attains this bound. Combining an edge-rooted even-cover theorem of Wigal, Yoo, and Yu (WYY) with an even-cover-to-walk lemma proved here yields this bound for adjacent terminals, a consequence not stated explicitly in their paper. We extend the bound to arbitrary terminal pairs. For cubic graphs, it becomes $\lfloor 5n/4 \rfloor$, to our knowledge the first direct $5/4$ bound for cubic path TSP that does not use the general path-to-tour reduction.

Comment
12 pages, 2 figures

Closest papers

Nearest neighbours by meaning across the whole index.

A Low-Diameter Nash-Williams--Tutte Theorem

cs.DM math.COcs.DS ·2026-11-03 ·Pin-Hsian Lee, Peng-Ting Lin, Meng-Tsung Tsai, Ting-An Wu
theory similarity 0.67
Abstract

The Nash-Williams--Tutte theorem characterizes the existence of $k$ edge-disjoint spanning trees by a condition on every vertex partition. We prove that, for simple graphs, the same condition guarantees $k$ edge-disjoint spanning trees, each of diameter $O(n/δ)$ and with $O((n/δ)\log(δ+1))$ internal vertices, where $n$ is the number of vertices and $δ$ is the minimum degree. Both bounds hold simultaneously for every tree, with absolute implicit constants independent of $k$, and each is asymptotically optimal in general. Our proof is constructive and yields a randomized algorithm with expected running time $\tilde{O}(n^5)$. We derive applications to short edge-disjoint routes and weak linkages, small Steiner trees, and survivable networks with short paths. The joint bounds also yield low-diameter spanning Eulerian subgraphs and short tours for postman and general routing problems.

0.29

An improved bound on the treewidth of planar graphs excluding a grid minor

cs.DM math.CO ·2026-09-14 ·Wouter Cames van Batenburg, Quentin Claus, Gwenaël Joret, Robin Petit, Jean-Florent Raymond +1 more
similarity 0.64
Abstract

We show that every planar graph with no $t \times t$ grid minor has treewidth at most $4t +4$. This improves on the previously best known bound of $\frac{9}{2}t - \frac{11}{2}$, due to Gu and Tamaki (2012), and is within a factor $2$ of optimal. A key step in the proof is showing the following result, which might be of independent interest: Every $2$-connected plane graph $G$ with radius $d$ and faces of size at most $k$ has a tree-decomposition of width at most $\max\{3d+ k+5, 2d+2k+1\}$ such that the vertex set of every face of $G$ is contained in some bag.

0.41

Coloring graphs with no long induced path

cs.DM math.CO ·2026-09-08 ·Sang-il Oum
similarity 0.64
Abstract · 8 pages; the bound is improved; Added references and clarified attribution of the proof methods

Let $P_t$ denote the induced path on $t$ vertices. Let $ω(G)$ denote the maximum number of vertices in a clique of a graph $G$. Gyárfás (1987) proved that every $P_t$-free graph $G$ satisfies $χ(G)\le(t-1)^{ω(G)-1}$, and Gravier, Hoàng, and Maffray (2003) improved this to $χ(G)\le (t-2)^{ω(G)-1}$ for $t\ge4$. We lower the base of the exponential by one: for every $t\ge5$, every $P_t$-free graph $G$ satisfies \[ χ(G)\le 3\,(t-3)^{ω(G)+4}. \] The proof combines two refinements of the Gyárfás path argument and was developed with the assistance of Claude Fable 5.1 of Anthropic and GPT Pro of OpenAI.

0.47

Polynomial pathwidth for graphs vertex-coverable by few shortest paths and algorithms for quasi-shortest path covers

cs.DM cs.DSmath.CO ·2026-10-21 ·Li-Hsuan Chen, Florent Foucaud, Ling-Ju Hung, Ralf Klasing, Lucas Lorieau +1 more
theory similarity 0.64
Abstract · 21 pages, 1 figure

We study how covering a graph by a small number of shortest or approximately shortest paths/walks constrains its treewidth and pathwidth. A path or walk is $(α,β)$-quasi-shortest for $α\geq1$ and $β\geq 0$ if each contiguous segment has length at most $α$ times the distance between its endpoints plus $β$. For graphs vertex-covered by $k$ shortest paths, we establish the first known polynomial pathwidth bound of $O(k^3)$. For edge-coverage, we improve the previously known $O(k^4)$ upper bound to $O(k^2\log k)$. As a main ingredient of the proofs, we first show that if the vertices of a graph can be covered by $k$ $(α,β)$-quasi-shortest paths or walks, then its treewidth is $O_{α,β}(k^2)$; this is a consequence of the fact that such graphs have linear metric growth and the technique developed in [Campbell et al., E-JC 2023]. To obtain the above pathwidth upper bounds, we combine this result with techniques from the literature in a nontrivial way. On the other hand, we show that there exist connected bipartite cubic graph whose edges can be covered by $k$ shortest paths and whose pathwidth is $Ω(k\log k)$, providing the first superlinear lower bound. For graphs covered by $k=2$ $(α,0)$-quasi-shortest paths with $α>1$, we show that, unlike treewidth and unlike the case $α=1$ and $β=0$ of exact shortest paths, the pathwidth may be unbounded. Finally, for every fixed rationals $α\geq1$ and $β\geq 0$, we give XP algorithms with a running time of $n^{f(k,α,β)}$ for some function~$f$ that decide whether the vertices of a graph can be covered by at most $k$ $(α,β)$-quasi-shortest paths or walks. The algorithms combine our treewidth upper bounds with an algorithmic meta-theorem from [Dreier et al., LICS 2025]. [abstract shortened to meet the arXiv requirements]

0.14

$K_h$-Minor-Free Graphs Have Balanced Separators of Size $O(h\sqrt{n})$

cs.DM math.CO ·2026-10-31 ·Jonathan Conroy, Hung Le, Jack Spalding-Jamieson
theory similarity 0.64
Abstract

We show that every $K_h$-minor-free graph with $n$ vertices has a balanced separator of size $O(h\sqrt{n})$ for any parameter $h \in \mathbb{N}$, resolving the conjecture posed by Alon, Seymour, and Thomas [AST90] in 1990. The proof is elementary, building on the combinatorial framework by Le [Le26]. A key new idea of the proof is the existence of a short hitting walk on vertex expanders: given $k$ large (not necessarily disjoint) subsets of vertices, there is a walk of length $O(k/ψ(G))$ hitting every subset, where $ψ(G)$ is the vertex expansion. This technical result substantially improves on an analogous lemma by Alon, Seymour, and Thomas [AST90] in an important parameter setting, where the previous lower bound [Kot00] does not apply.

0.48

Treewidth 3 in the Product Structure Theorem for Bounded Degree Graphs in Minor-Closed Classes

cs.DM math.CO ·2026-11-18 ·Vida Dujmović, Robert Hickingbotham, Pat Morin, David R. Wood
theory similarity 0.63
Abstract · 28 pages, 4 figures, written by humans

We show that, for all positive integers $t$ and $Δ$, there exists an integer $c$ such that, for every $K_t$-minor-free graph $G$ with maximum degree at most $Δ$, there exists a graph $H$ of treewidth at most $3$ and a path $P$ such that $G$ is isomorphic to a subgraph of the strong product $H\boxtimes P\boxtimes K_c$. This improves on a previous result of Dujumović, Esperet, Micek, Walczak, and Wood (2022) by bounding the treewidth of $H$ independently of $t$ and $Δ$. As an immediate consequence we obtain a bound of $O(r^4)$ on the $r$-weak colouring number of bounded-degree graphs from any proper minor-closed graph class.

0.21

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

cs.DS cs.DMmath.CO ·2026-11-03 ·Serge Gaspers
theory similarity 0.63
Abstract · Code, computer certificates and Lean 4 formal proofs: https://serggasp.github.io/pathwidth-site/ and https://doi.org/10.5281/zenodo.23883489

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π}\arccos\frac56\approx0.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 $\sum_{d\ge3}a_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$).

0.35

Linear-Time FPT Algorithm for Surface Disjoint Paths via Surface Cutting

cs.DS cs.CG ·2026-09-24 ·Kyungjin Cho, Eunjin Oh, Sebastian Wiederrecht
similarity 0.62
Abstract · To apear in ISAAC 2026

We study the \textsc{$k$-Disjoint Paths} problem on a graph embedded on a surface with bounded Euler genus. Given a graph $G$ with $n$ vertices and $k$ vertex pairs embedded on a surface of Euler genus $g$, we present a $2^{O(k^2+g^2)}n$-time algorithm that computes $k$ pairwise vertex-disjoint paths connecting the given vertex pairs if such paths exist. Our approach relies on the decomposition of $G$ into $O(k+g)$ planar subgraphs while bounding the complexity of the boundaries between these subgraphs. This approach enables the use of techniques for compressing linkages in planar graphs. Moreover, our techniques yield two kernels of size polynomial in $k$, $g$, and the treewidth of the graph, and of size $2^{O(k+g)}$. These results extend recent advances on \textsc{$k$-Disjoint Paths} on planar graphs [Cho et al. SODA 2023] and [Włodarczyk and Zehavi FOCS 2023] to surface-embedded graphs.

0.20