Lossy Kernelization
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Defines alpha-approximate kernel (polynomial-time reduction plus a solution lifting algorithm that turns any C-approximate solution of the reduced instance into an α·C-approximate solution for the original), proves: π has an FPT α-approximation iff π admits an α-approximate kernel. Uses standard kernel lower-bound machinery (Bodlaender/Downey/Fellows/Håstad and Fortnow–Santhanam plus Dell–van Melkebeek refinements). Gives constructive trade-offs: connected vertex cover admits polynomial-size α-kernels for every α>1 (size grows as α→1, collapsing to 2^k at α=1); longest path has no polynomial α-kernel; tree-deletion-set has polynomial kernel but no α-approximate polynomial kernel unless P=NP.
AI-written summary · about
chapters (11)
- 0:00Introduction to lossy kernelization
- 13:16Limitations of kernelization
- 18:59Alpha approximate kernelization
- 25:06Parameterized optimization framework
- 32:33Connected vertex cover example
- 40:58Kernelization for optimization
- 43:25Alpha approximate kernel definition
- 47:38FPT approximation equivalence
- 51:53Connected vertex cover results
- 57:06Open problems and future work
- 1:00:00Q&A
related talks
28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
A Formal Disproof of Hirsch Conjecture
16mCertification with an NP Oracle
23mWorst-Case to Expander-Case Reductions
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
01h 10mComplexity and Algorithmic Game Theory II
25mOn computing homological hitting sets
41mOn counting subgraphs and why counting seeds makes more sense (if one thinks about it clearly)