Parameterized Complexity of Isometric Path Partition: Treewidth and Diameter
Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, Prafullkumar Tale · 2025
Read Parameterized Complexity of Isometric Path Partition: Treewidth and Diameter by Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, Prafullkumar Tale (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2508-05448.txt.
Introduction
Dibyayan Chakraborty and co-authors wrote a paper in two thousand twenty-five about the difficulty of splitting a graph into shortest paths. The task, called isometric path partition, asks for a cover of all vertices by paths that are each as short as possible between their ends. Such metric problems often escape the general tools that solve many graph tasks by treewidth.
The authors prove the problem is hard for the treewidth parameter, in fact even for the stricter pathwidth, settling an open question. They also design a tailored dynamic programming algorithm whose running time grows in a stated way with treewidth and graph size. A second version ties the time to the graph's diameter as well. They rule out much faster algorithms.
Catalog record
| CREATOR | Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, Prafullkumar Tale |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 134 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2508-05448
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Parameterized Complexity of Isometric Path Partition: Treewidth and Diameter Dibyayan Chakraborty, Oscar Defrain, Florent Foucaud, Mathieu Mari, Prafullkumar Tale Abstract In the Isometric Path Partition problem, the input is a graph G G with n n vertices and an integer k k , and the objective is to determine whether the vertices of G G can be partitioned into k 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 1990 ] shows that graph problems that are expressible as MSO formulas of constant size admit 𝖥𝖯𝖳 \mathsf{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. In this paper, we prove that Isometric Path Partition is 𝖶 [ 1 ] {\mathsf{W}}[1] -hard when parameterized by treewidth (in fact, even pathwidth), answering the question by Dumas et al. [SIDMA, 2024], Fernau et al. [CIAC, 2023], and confirming the aforementioned tendency. We complement this hardness result by designing a tailored dynamic programming algorithm running in n O ( tw ) n^{O(\textsf{tw})} time. This dynamic programming approach also results in an algorithm running in time diam O ( tw 2 ) ⋅ n O ( 1 ) \smash{\textsf{diam}^{O(\textsf{tw}^{2})}\cdot n^{O(1)}} , where diam is the diameter of the graph. It is known that Isometric Path Partition remains 𝖭𝖯 \mathsf{NP} -hard on graphs of diameter 2 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 admit algorithms running in time 2 O ( tw ) ⋅ n O ( 1 ) 2^{O(\textsf{tw})}\cdot n^{O(1)} or 2 O ( tw log ( tw ) ) ⋅ n O ( 1 ) 2^{O(\textsf{tw}\log(\textsf{tw}))}\cdot n^{O(1)} . However, we rule out the possibility of a significantly faster algorithm by proving that Isometric Path Partition does not admit an algorithm running in time diam o ( tw 2 / ( log 3 ( tw ) ) ) ⋅ n O ( 1 ) \smash{\textsf{diam}^{o(\textsf{tw}^{2}/(\log^{3}(\textsf{tw})))}\cdot n^{O(1)}} , unless the Randomized-ETH fails. Keywords: Isometric Path Partition , parameterized complexity, parameterized reductions, treewidth, diameter, Randomized ETH. 1 Introduction In this paper, we investigate the parameterized complexity of a metric-based optimization problem known as Isometric Path Partition , that deals with partitioning the vertex set of an input graph into a given number of isometric (i.e., shortest) paths. Metric-based optimization problems. The main subject of metric graph theory is the investigation and characterization of graph classes and graph problems, where the graphs are equipped with a metric [ CCCJ24 , BC08 ] . It is a central topic in mathematics and computer science with far-reaching applications such as in group theory [ Gro87 , Ago13 ] , matroid theory [ BCK18 ] , learning theory [ CCI+23 , CCMW22 , CKP22 , CCIR24 ] , and computational biology [ BD92 ] . One of the most natural metrics related to graphs is the shortest-path distance between two vertices. On the algorithmic side, many problems related to network monitoring, transportation networks, information retrieval, or computational learning can often be formulated as problems on graphs in which the objective is to find vertices that satisfy specified distance-related properties. We use “metric-based optimization problems” as an umbrella term for such problems. This includes many important and classic graph problems, such as Single Source Shortest Paths , Distance d -Dominating Set (also called (k,d) -Center ), Distance d -Independent Set (also called d -Scattered Set ), Metric Dimension , Geodetic Set , Isometric Path Cover , etc. Some of these problems have been cornerstones in the development of classic as well as parameterized algorithms and complexity [ BFGR17 , KLP19 , LP22 , KLP22 , CFH25 , FGK+24 , BDMI25 ] , as they behave quite differently from their more “local” (neighborhood-based) counterparts such as Vertex Cover , Independent Set or Dominating Set . In parameterized analysis, we associate each instance I with a parameter \ell , and are interested in an algorithm with running time f(\ell)\cdot|I|^{O(1)} for some computable function f . Parameterized problems that admit such an algorithm are called fixed parameter tractable ( \mathsf{FPT} ) parameterized by \ell . On the other hand, {\mathsf{W}}[1] -hardness categorizes problems that are unlikely to have \mathsf{FPT} algorithms. A parameterized problem is in \mathsf{XP} if it admits an algorithm running in time |I|^{f(\ell)} for some computable function f . Limitations of Treewidth. A large class of problems admits \mathsf{FPT} algorithms when parameterized by the treewidth, a parameter that quantifies tree-likeness of the graph. Courcelle’s celebrated theorem [ Cou90 ] states that the class of graph problems expressible in Monadic Second-Order (MSO) Logic of constant size is fixed-parameter tractable ( \mathsf{FPT} ) when parameterized by the treewidth of the graph. We refer readers to [ CFK+15 , Chapter 7] for further details. Although one can express many of the graph properties using MSO formulas of constant size, there is no such formula to encode the following: given a subset of vertices and two specified vertices s,t , does this subset form an isometric path (i.e., a shortest path) between s and t [ Kup23 ] . This hinders the application of Courcelle’s theorem to metric-based optimization problems. Consider the example of Dominating Set and its generalization Distance d -Dominating Set . The objectives of these problems are to find a subset of vertices S such that any vertex in V(G)\setminus S is at distance at most 1 and at most d , respectively, from at least one vertex in S . As the distance requirement in the first problem is upper bounded by a constant, it is expressible as an MSO formula of constant size, resulting in an \mathsf{FPT} algorithm parameterized by treewidth. However, this is not the case for the latter problem. In fact, if d is part of the input, it is known that Distance d -Dominating Set is \mathsf{W} [1]-hard when parameterized by treewidth [ BL16 ] . There are similar results for Independent Set and its generalization Distance d -Independent Set [ KLP22 ] . Similarly, the metric-based optimization problems Geodetic Set and Metric Dimension are even \mathsf{NP} -hard when the treewidth of the graph is a constant [ LP22 , Tal25 ] . Hence, metric-based optimization problems require individual attention and often draw the boundary for the success story of parameterization by treewidth stemming from Courcelle’s theorem. Isometric Path Partition . Isometric (i.e., shortest) paths in graphs and vertex-partitioning are among the most fundamental constructs in the area of graph algorithms. In this article, we consider an interesting metric-based optimization problem known as Isometric Path Partition , whose objective is to partition the vertex