Independent Set on P_k-Free Graphs in Quasi-Polynomial Time

Explore a 23-minute IEEE conference talk on solving the Independent Set problem on P_k-Free Graphs in quasi-polynomial time. Learn about the problem definition, its NP-completeness, known polynomial-time classes, and results beyond polynomial time. Discover the presenters' novel algorithm, including its running time analysis, the Balanced Separator Lemma, and the process of collecting balanced separators. Gain insights into the concept of branchable vertices, the main lemma, and how the algorithm achieves its goals. Understand the upper bounds on level sets and how all components work together to solve this challenging computational problem.

Intro
Problem Definition
Independent Set One of Karp's 21 NP-complete problems
Independent Set is Hard
Known Polynomial Time classes
Known Results Beyond polyomial time
Our Results
All remaining cases in P?
Algorithm in a nutshell
Running time?
Balanced Separator Lemma
How to achieve goal?
Collecting Balanced Separators
Actual Algorithm
(Not So) Updated Goal
Branchable Vertex
Main Lemma
Upper bound on level sets
Putting it Together