Towards General and Tight Hardness Results for Graph Problems
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Shows specific reductions and constructions that give tight exponential lower bounds: a reduce from vertex cover on subcubic graphs using an alpha-sequence gadget that forces deleting one of two vertices per gadget, plus Theta(n) copies, yields no 2^{o(n+m)} lower bound for many Pi-vertex-deletion and Pi/F-partition problems when Pi contains all independent sets; uses large-girth instances to avoid gadget ambiguity, complements the argument when Pi omits independent sets, and extends to bounded-degree and planar variants with corresponding sqrt-n style bounds.
AI-written summary · about
chapters (9)
- 0:00Introduction
- 0:25Concrete Problem
- 5:56Vertex Cover Reduction
- 9:39All Construction
- 11:36Construction
- 14:49Reduction
- 15:56Exclude
- 17:55Future work
- 20:16Edge Deletion
related talks
59mHardness for Graph Problems - Reductions Based on APSP and SETH
35mSuperlinear Lower Bounds for Multipass Graph Processing
56mSatisfiability Algorithms II
01h 23mProperty Testing for Graphs
23mA New Connection Between Node and Edge Depth Robust Graphs
01h 05mGraph Algorithms in the MPC Model
51mAn Improved Bound for Regular Partitions of Hypergraph of Bounded VC_2 Dimension
01h 07mComputational Complexity of Polynomial Time Problems: Introduction