***********************************
                * Princeton Discrete Math Seminar *
                ***********************************

Speaker: Daniel Lokshtanov (UCSB)

Thursday 17th September, 15:00. Zoom link is
https://princeton.zoom.us/j/94439172371, and the password
will be mailed to the seminar and CLO mail list.


Title: Independent set on Pk-free graphs in quasi-polynomial time

We present an algorithm that takes as input a graph G with weights on
the vertices, and computes a maximum weight independent set S of G.
If the input graph G excludes a path Pk on  k vertices as an induced
subgraph, the algorithm runs in time n^O(k^2 (log n)^3). Hence,for
every fixed k our algorithm runs in quasi-polynomial time. This
resolves in the affirmative an open problem of [Thomasse, SODA’20
invited presentation]. Previous to this work, polynomial time
algorithms were only known for P4-free graphs [Corneil et al.,
DAM’81], P5-free graphs [Lokshtanov et al., SODA’14], and P6-free
graphs [Grzesik et al., SODA’19]. For larger values of t, only
2^O(sqrt{t*n*log n}) time algorithms [Bacso et al., Algorithmica’19]
and quasi-polynomial time approximation schemes [Chudnovsky et al.,
SODA’20] were known. Thus, our work is the first to offer conclusive
evidence that Independent Set on Pk-free graphs is not NP-complete
for any integer k.

Joint work with Peter Gartland (UCSB)


		----------------------------------

Next week: Isolde Adler 

Anyone wishing to be added to or removed from this mailing list should
contact Paul Seymour (pds@math.princeton.edu)