Quasi-polynomial-time algorithm for Independent Set in P_t-free and C_{>t}-free graphs via shrinking the space of connecting subgraphs

Speaker(s)

Marcin Pilipczuk

Date

Oct. 22, 2020, 12:15 p.m.

Information about the event

online

Seminar

Seminar Algorithms

---

In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020]
showed a quasi-polynomial-time algorithm for Maximum Weight Independent
Set in P_t-free graphs, that is, graphs excluding a fixed path as an
induced subgraph. Their algorithm runs in time n^O(log^3(n)), where t is
assumed to be a constant. Inspired by their ideas, we present an
arguably simpler algorithm with an improved running time bound of
n^O(log^2(n)). Our main insight is that a connected P_t-free graph
always contains a vertex w whose neighborhood intersects, for a constant
fraction of pairs {u, v} \in {V(G) \choose 2}, a constant fraction of
induced u-v paths. Since a P_t-free graph contains O(n^{t−1}) induced
paths in total, branching on such a vertex and recursing independently
on the connected components leads to a quasi-polynomial running time
bound. We also show that the same approach can be used to obtain
quasi-polynomial-time algorithms for related problems, including Maximum
Weight Induced Matching and 3-Coloring.

---