Subexponential Parameterized Complexity of Completion Problems: Survey of the Upper Bounds
Talkat Satisfiability Lower Bounds and Tight Results for Parameterized and Exponential-Time Algorithms · on Friday, 2015-11-06·
summary
Survey states that many graph completion problems (split, chordal, proper-interval, several others) admit subexponential FPT algorithms by enumerating a subexponential family of structures and doing DP over clique separators. Key concrete claims: there are n^{O(√k)} candidates for maximal cliques in a solution and that yields 2^{O(√k log k)} running time (equivalently k^{O(√k)} up to polylogs) for several classes. Interval completion is harder historically, polynomial kernels remain open, and the DP/branching framework is implemented and effective.
AI-written summary · about
chapters (11)
- 0:00Intro
- 1:20Graph modification problems
- 6:15Interesting classes for completion
- 9:51Finite set F
- 13:18Polynomial kernels
- 14:54Look at the bright side!
- 18:50Chordal completion
- 20:57Enumerating potential maximal cliques
- 22:26Maximal cliques in Interval Completion
- 27:06Summary
- 27:52Open problems
related talks
55mSiegel's Theorem, Edge Coloring, and a Holant Dichotomy
23mWorst-Case to Expander-Case Reductions
34mNew Tools for Peak Memory Scheduling
01h 32mInapproximability of Constraint Satisfaction Problems I
16mCertification with an NP Oracle
28mSettling the Pass Complexity of Approximate Matchings in Dynamic Graph Streams
25mExponential separations using guarded extension variables
18mCharacterizing the Multi-Pass Streaming Complexity for Solving Boolean CSPs Exactly