Nov 6, 2020, Pawel Rzazewski: Quasi-polynomial-time algorithms

Nov 6, 2020: Pawel Rzazewski (Warsaw University of Technology, Poland)

Title: Quasi-polynomial-time algorithms for independent set and related problems in P_t-free graphs
Abstract The complexity of the Independent Set problem in P_t-free graphs, i.e., graphs that do not contain a path on t vertices as an induced subgraph, is one of the main open problems concerning algorithms for restricted graph classes. The problem is known to be polynomial-time-solvable for t at most 6. Unfortunately the proof is fine-tailored for this class of graphs and our current algorithmic toolbox seems insufficient to provide a polynomial-time algorithm for P_t-free graphs, for every fixed t. In the recent breakthrough, Gartland and Lokshtanov (FOCS 2020) gave a quasi-polynomial-time algorithm for the problem in P_t-free graphs: their algorithm runs in time n^O(log^3n), where t is assumed to be a constant. Inspired by their ideas, Pilipczuk, Pilipczuk, and Rzazewski (accepted to SOSA 2021) showed an arguably simpler algorithm with an improved running time bound of n^O(log^2 n). During the talk I will present the simplified algorithm and discuss very recent extensions of this approach to different problems, including 3-Coloring and Feedback Vertex Set. Joint work with Peter Gartland, Daniel Lokshtanov, Marcin Pilipczuk, Micha‚ Pilipczuk.