Approximation and Fixed Parameter Subquadratic Algorithms for Radius and Diameter in Sparse Graphs
Talkat Computational Complexity of Low-Polynomial Time Problems (Simons Institute workshop, 2015) · on Tuesday, 2015-12-08
summary
Gives matching conditional upper and lower bounds: diameter needs a 3/2-approx in truly subquadratic time under Orthogonal Vectors, radius hardness comes from the Hitting Set conjecture, and source radius has a tight 2-approx. Presents fixed-parameter-subquadratic algorithms parameterized by treewidth that run roughly n·2^{O(k log k)} time and a reduction that embeds the quadratic hardness into graphs of small treewidth, yielding conditional lower bounds that rule out improving the dependence to n·2^{o(k)} while keeping truly subquadratic time.
AI-written summary · about
chapters (11)
- 0:00Intro
- 0:12Outline
- 0:52The Radius and DIAMETER Problems
- 2:12Directed Variants
- 5:47Hardness Conjectures To Radius/Diameter
- 8:35Our Results (Diameter Approximation)
- 9:52Our Results (Radius Approximation)
- 11:06Fixed Parameter Tractable in P
- 13:36Algorithms for Trees
- 16:08Algorithm Strategy
- 22:35Open Questions