标题： 参数化复杂性：等距路径划分，树宽和直径 显示英文标题

标题： Parameterized complexity of isometric path partition: treewidth and diameter

摘要： 我们研究当参数化为输入图的分枝宽度（$\mathrm{tw}$）时，等距路径划分问题的参数化复杂性，这可能是最广泛研究的参数之一。 Courcelle定理表明，可以作为常数大小MSO公式的图问题在参数化为输入图的分枝宽度时具有FPT算法。 这涵盖了众多自然的图问题。 然而，许多基于度量的图问题，其中解是基于图的某种度量属性（通常是距离）定义的，不能表示为常数大小的MSO公式。 这类问题，如等距路径划分问题，需要单独关注，并且常常成为分枝宽度参数化的成功故事的边界。 在本文中，我们证明当参数化为分枝宽度（实际上甚至路径宽度）时，等距路径划分问题是$W[1]$-难的，回答了Dumas等人[SIDMA, 2024]、Fernau等人[CIAC, 2023]提出的问题，并确认了上述趋势。 我们通过设计一个定制的动态规划算法来补充这一困难结果，该算法运行时间为$n^{O(\mathrm{tw})}$。 这种动态规划方法也导致了一个运行时间为$\textrm{diam}^{O(\mathrm{tw}^2)} \cdot n^{O(1)}$的算法，其中$\textrm{diam}$是图的直径。 请注意，对分枝宽度的依赖异常高，因为大多数问题的算法运行时间都是$2^{O(\mathrm{tw})}\cdot n^{O(1)}$或$2^{O(\mathrm{tw} \log (\mathrm{tw}))}\cdot n^{O(1)}$。 然而，我们通过证明等距路径划分问题在随机化ETH失败的情况下，无法在时间$\textrm{diam}^{o(\mathrm{tw}^2/(\log^3(\mathrm{tw})))} \cdot n^{O(1)}$内运行，从而排除了存在显著更快算法的可能性。 显示英文摘要

摘要： We investigate the parameterized complexity of the Isometric Path Partition problem when parameterized by the treewidth ($\mathrm{tw}$) of the input graph, arguably one of the most widely studied parameters. Courcelle's theorem 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. In this paper, we prove that Isometric Path Partition is $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(\mathrm{tw})}$ time. This dynamic programming approach also results in an algorithm running in time $\textrm{diam}^{O(\mathrm{tw}^2)} \cdot n^{O(1)}$, where $\textrm{diam}$ is the diameter of the graph. Note that the dependency on treewidth is unusually high, as most problems admit algorithms running in time $2^{O(\mathrm{tw})}\cdot n^{O(1)}$ or $2^{O(\mathrm{tw} \log (\mathrm{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 $\textrm{diam}^{o(\mathrm{tw}^2/(\log^3(\mathrm{tw})))} \cdot n^{O(1)}$, unless the Randomized-ETH fails.