Structural and algorithmic properties of hereditary graph classes

  project SONATA BIS, running July 2024 to June 2029. PI:

Our research lies on the boundary of structural and algorithmic graph theory.
The starting point is the long-standing open problem of complexity of problems like Maximum Independent Set in graph classes like graphs excluding a fixed path or subdivided claw (three-leaf tree) as induced subgraphs. There is an accelerated progress in recent years here.
We are also interested in related purely graph-theoretical questions such as chi-boundedness and the Erdos-Hajnal property in these and related graph classes.

Project's publications

1. Peter Gartland, Daniel Lokshtanov, Tomás Masarík, Main Pilipczuk, Michal Pilipczuk, Pawel Rzazewski: Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time. STOC 2024: 683-691, arXiv.
2. Tara Abrishami, Maria Chudnovsky, Marcin Pilipczuk, Pawel Rzazewski: Max Weight Independent Set in Sparse Graphs with No Long Claws. STACS 2024: 4:1-4:15, arXiv.
3. Maria Chudnovsky, Rose McCarty, Marcin Pilipczuk, Michal Pilipczuk, Pawel Rzazewski: Sparse induced subgraphs in P6-free graphs. SODA 2024: 5291-5299, arXiv.
4. Maria Chudnovsky, Jadwiga Czyzewska, Kacper Kluk, Marcin Pilipczuk, Pawel Rzazewski: Sparse induced subgraphs in P7-free graphs of bounded clique number. arXiv.
5. Marcin Pilipczuk, Pawel Rzazewski: A polynomial bound on the number of minimal separators and potential maximal cliques in P6-free graphs of bounded clique number. arXiv.
6. Hsien-Chih Chang, Vincent Cohen-Addad, Jonathan Conroy, Hung Le, Marcin Pilipczuk, Michal Pilipczuk: Embedding Planar Graphs into Graphs of Treewidth O(log^3 n). SODA 2025: 88-123, arXiv.
7. Romain Bourneuf, Marcin Pilipczuk: Bounding ε-scatter dimension via metric sparsit. SODA 2025: 3155-3171, arXiv.
8. Kacper Kluk, Marcin Pilipczuk, Michal Pilipczuk, Giannos Stamoulis: Faster diameter computation in graphs of bounded Euler genus. arXiv.
9. Tara Abrishami, Marcin Briański, Jadwiga Czyżewska, Rose MCarty, Martin Milanic, Pawel Rzazewski, Bartosz Walczak: Excluding a clique or a biclique in graphs of bounded induced matching treewidth. arXiv.

Exemplary Topics

Quasipolynomial-time algorithms

• QPTAS for Pt-free and Sttt-free graphs
• The clean n^O(log^2 n) algorithm for MIS in Pt-free graphs
• Earlier quasipolynomial-time algorithm of Peter and Daniel (more complicated)
• Generalizing to many problems (incl. Feedback Vertex Set) and C_{>t}-free graphs

Polynomial-time algorithms

• Classic Bouchitte-Todinca introducing the framework
• Modern dynamic programming with all MSO2 problems
• P5-free case
• P6-free case
• Containers (incl. simpler algorithm for the P5-free case)

Chi-boundedness

• Recent survey of Scott and Seymour
• Seymour's webpage with series of papers on Induced subgraphs of graphs with large chromatic number and Polynomial bounds for chromatic number

Erdos-Hajnal Conjecture

• Very recent exciting progress
• C5-free case
• Caterpillars
• Pt-free case
• Seymour's webpage with the series of papers on Pure pairs

Bootcamp

Positions

Postdoc

We are looking for a postdoc! The position is for two years, starting in October 2025. More details in the official annoucement.

PhD student (finished)

The call for PhD positions starting in October 2023 has finished. The stipend committee has decided to offer the positions to Jadwiga Czyzewska and Kacper Kluk, and evaluated all other applicants as not sufficiently qualified for the positions.