Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
复制标题
稀疏图中半径和直径的近似和固定参数次二次算法
DOI：
10.1137/1.9781611974331.ch28
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Joshua R. Wang
中科院分区：
文献类型：
--
作者：
Amir Abboud;Virginia Vassilevska Williams;Joshua R. Wang
半径和直径是基本的图参数，对于有向图有几种自然的定义。每个定义在各种应用中都有充分的动机。所有版本的直径和半径都可以通过求解所有点对之间的最短路径（APSP），然后进行快速的后处理步骤来解决。然而，即使在稀疏图中，在n个节点的图上求解APSP也需要Ω(n²)的时间。我们研究这样一个问题：在稀疏图中，直径和半径何时可以在真正的亚二次时间内解决，以及何时不太可能有这样的算法？由于我们在真正的亚二次时间内精确计算这些度量的条件下界，我们寻找近似和固定参数亚二次算法，或者寻找它们不存在的原因。我们发现：
• 在合理的假设下，大多数版本的直径和半径可以在真正的亚二次时间内以最优近似保证来解决。例如，对于具有单向距离的有向半径，存在一个时间复杂度为O(m[公式])的2 - 近似算法，而时间复杂度为O(n²⁻ᵉ)的(2 - Δ) - 近似算法被认为是不太可能的。
• 在树宽为k的图上，我们可以在2^O(k log k)n¹⁺ᵒ⁽¹⁾的时间内解决所有版本。我们表明这些算法接近最优，因为即使是一个时间复杂度为2^o(k)n²⁻ᵉ的(3/2 - Δ) - 近似算法也会反驳合理的假设。
这项工作的两个概念性贡献，我们希望能激发未来的研究，它们是：引入P中的固定参数可处理性框架，以及陈述正交向量猜想的一个不同量化变体，我们称之为击中集猜想。
The radius and diameter are fundamental graph parameters, with several natural definitions for directed graphs. Each definition is well-motivated in a variety of applications. All versions of diameter and radius can be solved via solving all-pairs shortest paths (APSP), followed by a fast postprocessing step. However, solving APSP on n-node graphs requires Ω(n2) time even in sparse graphs. We study the question: when can diameter and radius in sparse graphs be solved in truly subquadratic time, and when is such an algorithm unlikely? Motivated by our conditional lower bounds on computing these measures exactly in truly subquadratic time, we search for approximation and fixed parameter subquadratic algorithms, and alternatively, for reasons why they do not exist. We find that: • Most versions of Diameter and Radius can be solved in truly subquadratic time with optimal approximation guarantees, under plausible assumptions. For example, there is a 2-approximation algorithm for directed Radius with one-way distances that runs in O(m[EQUATION]) time, while a (2 -- Δ)-approximation algorithm in O(n2--e) time is considered unlikely. • On graphs with treewidth k, we can solve all versions in 2O(k log k)n1+o(1) time. We show that these algorithms are near optimal since even a (3/2 -- Δ)-approximation algorithm that runs in time 2o(k)n2--e would refute plausible assumptions. Two conceptual contributions of this work that we hope will incite future work are: the introduction of a Fixed Parameter Tractability in P framework, and the statement of a differently-quantified variant of the Orthogonal Vectors Conjecture, which we call the Hitting Set Conjecture.
影响因子：
2.4
作者：
Eriksson,Kimmo;Bailey,DrewH;Geary,DavidC
通讯作者：
Geary,DavidC