Paper Info
Title
Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs.
Abstract
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 Õ(m[EQUATION]) time, while a (2 -- δ)-approximation algorithm in O(n2--ε) 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--ε 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.
Year
DOI
Venue
2016
10.5555/2884435.2884463
SODA '16: Symposium on Discrete Algorithms Arlington Virginia January, 2016
Field
DocType
ISBN
Discrete mathematics,Graph,Combinatorics,Algorithm,Directed graph,Orthogonality,Treewidth,Conjecture,Mathematics
Conference
978-1-61197-433-1
Citations 
PageRank 
References 
21
0.74
32
Authors
3
Name
Order
Citations
PageRank
Abboud, A.141125.21
Virginia Vassilevska Williams2106660.36
Joshua R. Wang3695.83