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

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.