Papers for

network layout planners

Papers whose findings have a practical use for this group, as judged from the abstract. Open a paper to read what it means in practice.

Isometric path cover problem hard even on low treewidth graphs

Parameterized Complexity of Isometric Path Cover: Treewidth and Diameter

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.

Thu 15 OctData Structures and AlgorithmsComputational Complexity
The gist
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.
Open → 2610.22010v1