Parameterized Complexity of Isometric Path Partition: Treewidth and Diameter

Abstract

In the Isometric Path Partition problem, the input is a graph G with n vertices and an integer k, and the objective is to determine whether the vertices of G can be partitioned into k vertex-disjoint shortest paths. We investigate the parameterized complexity of the problem when parameterized by the treewidth (tw) of the input graph, arguably one of the most widely studied parameters. Courcelle’s theorem [Information & Computation, 1990] shows that graph problems that are expressible as MSO formulas of constant size admit FPT algorithms parameterized by the treewidth of the input graph. This encompasses many natural graph problems. However, many metric-based graph problems, where the solution is defined using some metric-based property of the graph (often the distance) are not expressible as MSO formulas of constant size. These types of problems, Isometric Path Partition being one of them, require individual attention and often draw the boundary for the success story of parameterization by treewidth. We show that Isometric Path Partition is W[1]-hard when parameterized by treewidth (in fact, even pathwidth (pw)), answering the question by Dumas et al. [SIDMA, 2024], Fernau et al. [TCS, 2025], and confirming the aforementioned tendency. We complement this hardness result by designing a tailored dynamic programming algorithm running in n^{O(tw)} time. This dynamic programming approach also results in an algorithm running in time diam^{O(tw²)} ⋅ n^{O(1)}, where diam is the diameter of the graph. It is known that Isometric Path Partition remains NP-hard on graphs of diameter 2; hence, the combination of both parameters is necessary to obtain a tractable algorithm. Note that the dependency on treewidth is unusually high, as most problems that are FPT for treewidth admit algorithms running in time 2^{O(tw)}⋅ n^{O(1)} or 2^{O(tw log (tw))}⋅ n^{O(1)}. However, we rule out the possibility of a significantly faster algorithm, showing that Isometric Path Partition does not admit an algorithm running in time diam^{o(pw²/(log³(pw)))} ⋅ n^{O(1)}, assuming the Randomized-ETH.