Class Central is learner-supported. When you buy through links on our site, we may earn an affiliate commission.

YouTube

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

IEEE via YouTube

Overview

Save Big on Coursera Plus. 7,000+ courses at $160 off. Limited Time Only!
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.

Syllabus

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

Taught by

IEEE FOCS: Foundations of Computer Science

Reviews

Start your review of Independent Set on P_k-Free Graphs in Quasi-Polynomial Time

Never Stop Learning.

Get personalized course recommendations, track subjects and courses with reminders, and more.

Someone learning on their laptop while sitting on the floor.