Recent Advances in FPT and Exact Algorithms for NP-Complete Problems
summary
Covers recent progress on fixed-parameter tractable (FPT) algorithms and exact exponential-time algorithms for NP-complete problems, focusing on algorithmic techniques and theoretical improvements. Discusses concrete methods used to design faster FPT and exact algorithms and trade-offs between parameterization and running time.
AI-written summary · about
chapters (22)
- 0:00Intro
- 0:33Overview
- 1:01Parameterized problems
- 2:31Parameterized complexity
- 5:30Fixed-parameter tractability
- 6:06FPT techniques
- 7:13W[1]-hardness
- 7:47Games to play
- 11:53Error probability
- 13:07Finding a path colored 1 - 2 - ...-k
- 13:55Improved Color Coding
- 16:03Derandomized Color Coding
- 20:40Solving the Party Problem
- 28:14Number of subproblems for HAMILTONIAN CYCLE
- 29:56Cut and count
- 30:33Isolation Lemma
- 32:14Cycle covers
- 35:54Treewidth
- 43:01Minors
- 43:53Planar Excluded Grid Theorem
- 52:37Square root phenomenon for planar graphs
- 54:02Wrap up
related talks
01h 21mComputational Complexity in Theory and in Practice
29mAn Isomorphism Between Parameterized Complexity and Classical Complexity, for both Time and Space
31mSome Novel Computational Models to Think About
23mTowards General and Tight Hardness Results for Graph Problems
30mLocal Problems on Trees from the Perspectives of Distributed Algorithms, Finitary Factors, and Descr
44mAlgorithmic Pirogov-Sinai Theory
35mApproximation hardness and online algorithms for resource scheduling
01h 05mGraph Algorithms in the MPC Model