Isometric path cover problem hard even on low treewidth graphs
Parameterized Complexity of Isometric Path Cover: Treewidth and Diameter
Data Structures and AlgorithmsComputational Complexity
Summary
The paper looks at a problem where you want to cover all points in a network with shortest possible paths. The authors find that this problem is very hard to solve even for networks that are structurally simple in certain ways. They also show that if you combine two measures of the network’s shape, called treewidth and diameter, there is a way to solve it that's possible but still quite slow. Finally, they prove that trying to solve the problem by focusing only on one of these measures is unlikely to work efficiently.
What this means in practice
- •For graph algorithm designers: Exclude efficient treewidth-based methods for isometric path cover and focus on combined parameters instead.
- •For network layout planners: Understand limitations of covering networks with shortest paths on tree-like structures to better estimate computational costs.
A theory result. No direct application yet.
Authors
Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, Prafullkumar Tale
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.