CS Paper Radar

Parameterized Complexity of Isometric Path Cover: Treewidth and Diameter

Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, Prafullkumar Tale

cs.DS cs.CC ·submitted 2026-10-15 14:51 UTC · v1

Abstract

We study the fixed-parameter tractability of the \textsc{Isometric Path Cover} problem where, given an integer $k$ and a simple, undirected, and unweighted graph $G$, the objective is to decide whether $G$ admits a set of $k$ isometric paths (i.e., shortest paths between their endpoints) whose union is the entire vertex set of $G$. We show that \textsc{Isometric Path Cover} is NP-hard on graphs of pathwidth (and thus treewidth) at most 287. This is an interesting contrast with the closely related problems \textsc{Isometric Path Partition} and \textsc{Path Cover}, which are both known to be XP for treewidth, see [Chakraborty et al., WG 2026] and [Foucaud et al., TCS 2026]. On the positive side, we show, by a suitable dynamic programming scheme, that \textsc{Isometric Path Cover} admits an XP algorithm w.r.t.~the parameter combination of treewidth and diameter, running in time $n^{\diam^{O(\tw)}}$ where $\diam$, $\tw$, and $n$ denote the diameter, the treewidth, and the number of vertices of the input graph, respectively. However, we also prove that \textsc{Isometric Path Cover} becomes W[1]-hard for pathwidth on graphs of diameter~7, showing that an XP algorithm is the best one can hope for w.r.t.~this parameterization, under standard complexity theory assumptions.

Closest papers

Nearest neighbours by meaning across the whole index.

Eccentricity Shortest Path: the structural parameter landscape

cs.DS math.CO ·2026-10-14 ·Anand Babu, Ashwin Jacob, Hitendra Kumar, R. B. Sandeep
theory similarity 0.76
Abstract · 74 pages, short abstract for arXiv

The Eccentricity Shortest Path problem asks, given a connected graph and a nonnegative integer $R$, whether some shortest path is within distance $R$ of every vertex. We study its structural parameterized complexity. We give fixed-parameter algorithms for vertex-deletion distance to cographs, vertex-deletion distance to interval graphs, and bandwidth. The interval-deletion result answers a question of Bhyravarapu et al. (IWOCA 2023). We obtain XP algorithms for vertex-deletion distance to chordal graphs, clique-width, and rank-width, without requiring expressions or decompositions for the latter two. Consequently, the problem is polynomial-time solvable for every fixed treewidth, answering a question of Chakraborty et al. (2026). We also derive fixed-parameter tractability for treedepth and XP membership for diameter from earlier algorithms. We prove $\mathsf{W}[3]$-hardness for cutwidth, and hence pathwidth and treewidth, even on graphs of maximum degree at most five; $\mathsf{W}[2]$-hardness for vertex clique-cover number; and NP-hardness on graphs of tree-independence number at most two. For maximum leaf number $\ell$, we obtain an $O(\ell^4)$-bit compression and a polynomial kernel. Finally, unless $\mathsf{NP}\subseteq\mathrm{coNP}/\mathrm{poly}$, we exclude polynomial kernels for bandwidth, feedback edge number, vertex-deletion distance to a clique, and vertex cover number. The last bound also excludes polynomial kernels for vertex-deletion distance to proper interval graphs.

0.24

Metric Dimension Parameterized by Bag-Connected Treewidth and Bag-Connected Pathwidth

cs.CC ·2026-11-06 ·Dibyayan Chakraborty, Sebastian Ordyniak, Sebastian Siebertz
theory similarity 0.74
Abstract

The metric dimension of a graph is the minimum size of a set of vertices whose distance vectors distinguish all vertices of the graph. We prove that \MetricDimension{} is NP-complete on planar graphs of treewidth and bag-connected treewidth exactly three. The graphs in our construction have no induced cycle longer than four and have (prefix-connected) pathwidth at most four. In particular, the problem admits no XP algorithm parameterized by bag-connected treewidth unless $\mathrm P=\mathrm{NP}$. This answers questions of Bonnet and Purohit and of Bousquet, Deschamps, and Parreau. We prove that the problem is fixed-parameter tractable when parameterized by bag-connected pathwidth.

0.17

A Faster Algorithm for Fewer Vertex-Disjoint Paths Parameterized by Treewidth

cs.DS cs.CC ·2026-09-24 ·DongYun Byun, Akira Matsubayashi
theory similarity 0.72
Abstract · 22 pages, 1 figure. Presented in IPEC 2026

The $k$ vertex-disjoint paths problem asks whether, given a graph $G$ and $k$ pairs of vertices $(s_1,t_1)$, \ldots, $(s_k,t_k)$, $G$ has $k$ pairwise vertex-disjoint paths connecting $s_i$ and $t_i$ for all $1\leq i\leq k$. If $G$ is undirected, then this problem is NP-complete, but there exist FPT algorithms parameterized by $k$.Since these algorithms involve an extremely large function on $k$, algorithms for restricted graphs have also been investigated. In particular, a $2^{2tw\log tw+O(tw)}\cdot n$ time algorithm for undirected graphs with $n$ vertices and treewidth $tw$ is proposed by Scheffler (Technical Report 396, TU Berlin, '94), and it is proved by Lokshtanov, Marx, and Saurabh (SIAM J. Comput. '18) that, under the ETH, there exists no $2^{o(pw\log pw)}\cdot n^{O(1)}$ time algorithm for either directed or undirected graphs with pathwidth $pw$ and for $k=Ω(pw^4)$. It has not been known whether the lower bound also holds for a smaller $k$. In this paper, we prove that, for both the directed and undirected cases, there is an algorithm faster than Lokshtanov et al.'s lower bound for $k=tw^{o(1)}$ by proposing a $2^{O((tw+k)\log k)}\cdot n$ time algorithm. Besides, we prove a lower bound that, under the SETH, there exists no $(2-ε)^{pw\log pw}\cdot n^{O(1)}$ time algorithm for directed graphs and for a general $k$. This lower bound is tight because, with slight modifications, Scheffler's algorithm runs in $2^{pw\log pw+O(pw)}\cdot n$ time also for directed graphs.

0.26

Path Length Existence Problems in Bounded-Treewidth Probabilistic Graphs

cs.DB cs.CC ·2026-10-13 ·Antoine Amarilli, Mikaël Monet, Harshul Sagar
hot direction similarity 0.70
Abstract · 42 pages

We consider the problem of computing the probability of existence of a source-to-target path or walk satisfying a given length constraint in an input probabilistic graph. The length constraints we consider can require the length to be at least $\ell$, at most $\ell$, or exactly $\ell$, for $\ell$ a target length given as input. The probabilistic graphs that we consider are directed graphs where each edge is annotated with an independent probability of existence. As this task is generally intractable (#P-hard), we aim for algorithms applying to input graphs that are assumed to be of bounded treewidth. We classify the complexity landscape of these problems: - We give an XP algorithm parameterised by treewidth to compute the probability that an input probabilistic graph contains a source-to-target path/walk of length $\geq \ell$, and do the same for a path/walk of length $\leq \ell$. - We show that the four problems mentioned in the last item are W[1]-hard parameterised by pathwidth (hence not FPT under the standard assumption that FPT$\neq$W[1]). This is in contrast to the case of non-probabilistic graphs, where the corresponding problems were known to be FPT parameterised by treewidth; and to the connectivity problem (and more generally MSO evaluation) on probabilistic graphs, where the same was known. - Surprisingly, we show that it is #P-hard to compute the probability that an input graph contains a source-to-target path/walk of length exactly $\ell$, even on graphs of pathwidth $2$. By contrast, all our problems are tractable on graphs of treewidth $1$. - Last, we investigate the complexity of our problems when the edges can carry weights. This causes all our problems to become #P-hard already on pathwidth-2 graphs, and causes specifically the ``exactly $\ell$'' walk problem to be #P-hard even on pathwidth-1 graphs.

0.32

Not All Degree Constraints Are Created Equal when Computing Spanning Trees

cs.DS ·2026-08-26 ·Narek Bojikian, Alexander Firbas, Robert Ganian, Hung P. Hoang, Krisztina Szilagyi
publishedtheory similarity 0.69
Abstract · To appear at IPEC 2026. This is the original submitted version - reviewer comments will be incorporated in a later version

We study the computation of minimum spanning trees subject to local degree constraints. Recent work (ICALP 2026) established that three natural formalizations of this problem share the exact same parameterized complexity under standard structural graph parameters, including treewidth, pathwidth and clique-width. This applies to the cases where every vertex has a single target degree (Specified Degree MST), or a degree upper bound (Bounded Degree MST), or is equipped with a set of admissible degrees (Set of Degrees MST). In this paper, we investigate these problems under more restrictive parameterizations and reveal that their complexity landscapes fundamentally diverge on bounded-treedepth graphs. Specifically, we prove that the former two problems are fixed-parameter tractable when parameterized by the treedepth of the input graph. In sharp contrast, we show that Set of Degrees MST remains W[1]-hard parameterized by treedepth, even when combined with the feedback vertex number (i.e., deletion distance to treewidth $1$). Finally, we show that this divergence seems to be specific to treedepth: we exclude an analogous W[1]-hardness result for Set of Degrees MST w.r.t. the vertex cover number and also rule out fixed-parameter algorithms for the former two problems w.r.t. deletion distance to constant pathwidth.

0.19

Where Treewidth and Pathwidth Diverge: Towards a Uniform Kernel for Pathwidth-$η$ Deletion

cs.DS cs.CC ·2026-08-10 ·Ahmed Ghazy, Jakob Greilhuber, Tim A. Hartmann, Roohani Sharma
publishedtheory similarity 0.68
Abstract

For a constant $η\geq 0$, Pathwidth-$η$ Deletion is the problem of deciding whether, for a given graph $G$ and integer $k$, there is a set $S \subseteq V(G)$ of size at most $k$ such that the pathwidth of $G - S$ is at most $η$. The problems Treewidth-$η$ Deletion and Treedepth-$η$ Deletion are defined similarly for the parameters treewidth and treedepth, respectively. A landmark result of Fomin et al. [FOCS, 2012] shows that, for any constant $η$, all three problems admit a kernel on $O(k^{c(η)})$ vertices, where $c(η)$ is a constant depending on $η$. Giannopoulou et al. [ACM TALG, 2017] show that, in some sense, this result is optimal for Treewidth-$η$ Deletion: for $η\geq 2$ and even when parameterizing by the size of a vertex cover $M$ of the input graph, there is no kernel of size $O(|M|^{\frac{η+1}{2}-\varepsilon})$, for any $\varepsilon > 0$. Contrasting this result, they prove that Treedepth-$η$ Deletion admits a uniform polynomial kernel, that is, a kernel of size $O(k^c)$ for a constant $c$ that is independent of $η$. In comparison, the question whether Pathwidth-$η$ Deletion admits a uniform polynomial kernel has been neglected in the literature. As treewidth and pathwidth tend to behave similarly, it is natural to expect that no uniform kernel exists when parameterizing by the size of a vertex cover. Surprisingly, we show this not to be the case. More concretely, we prove the existence of a uniform polynomial kernel for Pathwidth-$η$ Deletion when parameterizing by (1) the solution size $k$ plus the size of a set $M$ such that $G - M$ has bounded treedepth; (2) the (vertex-deletion) distance to pathwidth-$1$ graphs; (3) the distance to the class of graphs with treedepth at most $η+ 1$. This leads us to conjecture that Pathwidth-$η$ Deletion admits a uniform kernel when parameterizing by the solution size $k$.

0.50

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.68
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

A Polynomial-Time Algorithm for $k$-Path Vertex Cover Reconfiguration on Trees under Token Sliding

cs.DS cs.DM ·2026-10-22 ·Duc A. Hoang
similarity 0.67
Abstract

A $k$-path vertex cover ($k$-PVC) of a graph is a set of vertices meeting every path on $k$ vertices. In Token Sliding, one token occupies each vertex of a cover; a move slides one token along an edge to an unoccupied vertex, preserving the cover property. We study whether two covers of a tree are joined by such moves. The case $k=2$ admits a linear-time decision algorithm. For every integer $k\geq2$, we give an $O(kn^2)$-time decision algorithm on trees of order $n$, with $k$ part of the input. Two covers are reachable precisely when their rigid tokens, which never move, occupy the same set and every component remaining after their deletion has the same token count. The proof transforms configurations of equal size without rigid tokens into a canonical configuration built on properly rooted subtrees, whose paths on $k$ vertices pass through their roots. A rooted-subtree recurrence identifies movable candidate tokens. We also give a direct recursive construction between the supplied endpoints, returning at most $8n^2\,3^{\lceil n/2\rceil}$ slides in $O(n^{10}3^{n/2})$ time. ChatGPT 6 Pro and Claude Fable 5.1 were used to assist with developing and reviewing mathematical arguments and drafting and revising the paper. The author takes full responsibility for the correctness and content of the paper.

0.20