计算机科学 > 数据结构与算法
[提交于 2025年8月7日
]
标题: 参数化复杂性:等距路径划分,树宽和直径
标题: 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)}$内运行,从而排除了存在显著更快算法的可能性。
文献和引用工具
与本文相关的代码,数据和媒体
alphaXiv (什么是 alphaXiv?)
CatalyzeX 代码查找器 (什么是 CatalyzeX?)
DagsHub (什么是 DagsHub?)
Gotit.pub (什么是 GotitPub?)
Hugging Face (什么是 Huggingface?)
带有代码的论文 (什么是带有代码的论文?)
ScienceCast (什么是 ScienceCast?)
演示
推荐器和搜索工具
arXivLabs:与社区合作伙伴的实验项目
arXivLabs 是一个框架,允许合作伙伴直接在我们的网站上开发和分享新的 arXiv 特性。
与 arXivLabs 合作的个人和组织都接受了我们的价值观,即开放、社区、卓越和用户数据隐私。arXiv 承诺这些价值观,并且只与遵守这些价值观的合作伙伴合作。
有一个为 arXiv 社区增加价值的项目想法吗? 了解更多关于 arXivLabs 的信息.