#### Published and accepted for publication

21. Shaohua Li, Qilong Feng, Xiangzhong Meng, Jianxin Wang

**An Improved FPT Algorithm for the Flip Distance Problem**

20. Jiehua Chen, Danny Hermelin, Manuel Sorge

**On Computing Centroids According to the \(p\)-Norms of Hamming Distance Vectors**

19. Jiehua Chen, Piotr Skowron, Manuel Sorge

**Matchings under Preferences: Strength of Stability and Trade-offs**

18. Laurent Bulteau, Niels Grüttemeier, Christian Komusiewicz, Manuel Sorge

**Your Rugby Mates Don’t Need to Know your Colleagues: Triadic Closure with Edge Colors**

17. Robert Bredereck, Christian Komusiewicz, Stefan Kratsch, Hendrik Molter, Rolf Niedermeier, Manuel Sorge

**Assessing the Computational Complexity of Multi-Layer Subgraph Detection**

16. Jiehua Chen, Ondrej Suchy, Hendrik Molter, Manuel Sorge

**Cluster Editing in Multi-Layer and Temporal Graphs**

15. Iyad A. Kanj, Christian Komusiewicz, Manuel Sorge, Erik Jan van Leeuwen

**Solving Partition Problems Almost Always Requires Pushing Many Vertices Around**

14. Tomáš Masařík

**Flexibility of planar graphs without 4-cycles**

Using the discharging technique, we show that lists of size 5 are

sufficient for a planar graph without 4-cycles to be \(\varepsilon\)-Flexible, for

some constant \(\varepsilon\)

13. William Evans, Paweł Rzążewski, Noushin Saeedi, Chan-Su Shin, Alexander Wolff

**Representing Graphs and Hypergraphs by Touching Polygons in 3D**

preprint, *GD 2020*

We study contact representations with convex polygons in 3d and show that every graph admits such a representation.

12. Stephan Kreutzer, Irene Muzi, Patrice Ossona de Mendez, Roman Rabinovich, Sebastian Siebertz

**Algorithmic Properties of Sparse Digraphs**

We study the notions of directed bounded expansion and nowhere crownfulness on directed graphs, introduced by Kreutzer and Tazari in 2012.

11. Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé

**Quasi-polynomial time approximation schemes for the Maximum Weight Independent Set Problem in H-free graphs**

preprint, *accepted at SODA 2020*

We show that every class of graphs excluding a fixed forest of subdivided claws as an induced subgraph admits a quasi-polynomial-time approximation scheme for the Maximum Weight Independent Set problem.

10. Vincent Cohen-Addad, Marcin Pilipczuk, Michał Pilipczuk

**A Polynomial-Time Approximation Scheme for Facility Location on Planar Graphs**

preprint, *accepted at FOCS 2019*

We show a polynomial-time approximation scheme for the Facility Location problem in planar graphs.

9. Tomás Masarík, Irene Muzi, Marcin Pilipczuk, Pawel Rzazewski, Manuel Sorge

**Packing directed circuits quarter-integrally**

We show that the directed treewidth of a graph is bounded

by a cubic polynomial of the maximum size of quarter-integral packing of cycles. This proves a quartic relation between the feedback vertex set number and the maximum size of a quarter-integral cycle packing in a directed graph.

8. Wojciech Czerwinski, Wojciech Nadara, Marcin Pilipczuk

**Improved bounds for the excluded-minor approximation of treedepth**

We show that every graph of treewidth less than \(a\) and with no subcubic tree of treedepth \(b\) as a subgraph has treedepth \(O(ab)\). This has some consequences for approximation algorithms for treedepth.

7. Vincent Cohen-Addad, Marcin Pilipczuk, Michał Pilipczuk

**Efficient Approximation Schemes for Uniform-Cost Clustering Problems in Planar Graphs**

We show a facility coreset and a bicriteria approximation scheme for for the \(k\)-median problem in planar graphs.

6. Anita Liebenau, Marcin Pilipczuk, Paul D. Seymour, Sophie Spirkl

**Caterpillars in Erdős-Hajnal**

We prove that for every subdivision of a caterpillar \(T\), the class of graphs excluding both \(T\) and its complement satisfies the Erdős-Hajnal conjecture.

**On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs**We investigate the existence of subexponential parameterized algorithms in planar graphs. We show that, when parameterized by the number of terminals, such an algorithm exists for the Directed Subset TSP problem, while an existence of such an algorithm for Steiner Tree would contradict the Exponential Time Hypothesis. The latter result resolves a long-standing open problem in the area.

4. Stefan Kratsch, Shaohua Li, Marcin Pilipczuk, Magnus Wahlström

**Multi-budgeted Cuts**

We study a multi-budgeted variants of the minimum cut problem, the skew multicut problem, and the directed feedback arc set problem. Here, the edges of the graph are assigned colors and a separate cut budget is given for each of the colors. We give FPT algorithms for the considered problems, parameterized by the sum of all budgets. Furthermore, we show an extremal result bounding the number of maximally pushed solutions in the Chain SAT problem and the bounded-cardinality minimum-weight cut problem.

3. Shaohua Li, Marcin Pilipczuk

**An improved FPT algorithm for Independent Feedback Vertex Set**

We show a deterministic FPT algorithm for Independent Feedback Vertex Set with running time bound \(O^\ast((2+\phi)^k)\), where \(\phi\) is the golden ratio, matching the fastest known deterministic FPT algorithm for the classic Feedback Vertex Set problem.

2. Gábor Bacsó, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Zsolt Tuza, Erik Jan van Leeuwen

**Subexponential-time Algorithms for Maximum Independent Set in \(P_t\)-free and Broom-free Graphs**

preprint*, Algorithmica*

Among a number of related results, we show that Maximum Independent Set admits a subexponential algorithm with running time bound \(2^{O(t\sqrt{n \log n})}\) in \(P_t\)-free graphs.

**An exponential lower bound for cut sparsifiers in planar graphs**For an edge-weighted graph \(G\) with a set of \(k\) terminals, a mimicking network is a network with the same set of terminals that preserves sizes of minimum cuts between every partition of terminals. We show that in planar graphs, a mimicking network may require up to \(2^{k-2}\),

nearly matching the known upper bounds.

#### Preprints

M7. Marcelo Garlet Millani, Hendrik Molter, Rolf Niedermeier, Manuel Sorge

**Efficient Algorithms for Measuring the Funnel-likeness of DAGs**

M6. Jiehua Chen, Danny Hermelin, Manuel Sorge

**A Note on Clustering Aggregation**

M5. Julien Baste, Michael R. Fellows, Lars Jaffke, Tomáš Masařík, Mateus de Oliveira Oliveira, Geevarghese Philip, Frances A. Rosamond

**Diversity in Combinatorial Optimization**

We study a notion of diversity in the world of parameterized complexity. We provide a general tool that converts a wast majority of tree-decomposition based dynamic programs into the ones giving a set of diverse solution in FPT time.

M4. Wojciech Nadara, Marcin Smulewicz

**Decreasing maximum average degree by deleting independent set or d-degenerate subgraph**

We show that in every graph there exists an independent set

whose removal decreases maximum average degree by at least one.

M3. Maria Chudnovsky, Marcin Pilipczuk, Michal Pilipczuk, Stéphan Thomassé

**On the Maximum Weight Independent Set Problem in graphs without induced cycles of length at least five**

We show that in long-hole-free graphs (graph with no induced cycle of length at least five) one can find a maximum-weight independent set in time \(n^{O(k)}\) where \(k\) is the largest size of a prism in the graph.

M2. Marek Cygan, Pawel Komosa, Daniel Lokshtanov, Michal Pilipczuk, Marcin Pilipczuk, Saket Saurabh, Magnus Wahlström

**Randomized contractions meet lean decompositions**

We prove in an elegant way that for every graph \(G\) and an integer \(k\), one can compute a tree decomposition of \(G\) whose every adhesion is of size at most \(k\) while every bag cannot be nontrivially broken with a separation of order at most \(k\). The running time of the procedure is fixed-parameter tractable in \(k\), improving state-of-the-art FPT algorithms for a number of problems, including the Minimum Bisection problem.

M1. Jeremy Kun, Michael P. O’Brien, Marcin Pilipczuk, Blair D. Sullivan

**Polynomial Treedepth Bounds in Linear Colorings**

We define a notion of a linear coloring, where every path in a graph contains a vertex of a unique color on the path. We relate this notion to the classic notion of centered colorings (where every connected subgraph is required to contain a uniquely colored vertex).

#### Preliminary research

These few papers have been developed before the start of the grant CUTACOMBS (and were financed from other sources), but are closely related to the topic of the grant

and can be considered as a preliminary research for our goals.

P4. Andrzej Grzesik, Tereza Klimosova, Marcin Pilipczuk, Michal Pilipczuk

**Polynomial-time algorithm for Maximum Weight Independent Set on \(P_6\)-free graphs**

We show that the Maximum Independent Set problem is polynomial-time solvable in \(P_6\)-free graphs. On technical level, the paper builds on and extends the approach via potential maximal cliques that allowed Lokshtanov, Vatshelle, and Villanger to obtain a similar result in \(P_5\)-free graphs.

**Subexponential Parameterized Algorithms for Planar and Apex-Minor-Free Graphs via Low Treewidth Pattern Covering**We prove the following theorem.

Given a planar graph \(G\) and an integer \(k\), it is possible in polynomial time to randomly sample a subset \(A\) of vertices of \(G\) with the following properties:

- \(A\) induces a subgraph of \(G\) of treewidth \(\mathcal{O}(\sqrt{k}\log k)\), and
- for every connected subgraph \(H\) of \(G\) on at most \(k\) vertices, the probability that \(A\) covers the whole vertex set of \(H\) is at least \((2^{\mathcal{O}(\sqrt{k}\log^2 k)}\cdot n^{\mathcal{O}(1)})^{-1}\), where \(n\) is the number of vertices of \(G\).

Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential parameterized algorithms for problems on planar graphs, usually with running time bound \(2^{\mathcal{O}(\sqrt{k} \log^2 k)} n^{\mathcal{O}(1)}\).

The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph; examples of such problems include

Directed \(k\)-Path, Weighted \(k\)-Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others.

Up to this point, it was open whether these problems can be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality.

Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface.

**Subexponential parameterized algorithms for graphs of polynomial growth**We show that for a number of parameterized problems for which only single-exponential time algorithms are known on general graphs, subexponential parameterized algorithms with running time \(2^{\mathcal{O}(k^{1-\frac{1}{1+d}} \log^2 k)} n^{\mathcal{O}(1)}\) are possible for graphs of polynomial growth with growth rate (degree) \(d\), that is, if we assume that every ball of radius \(r\) contains only \(\mathcal{O}(r^d)\) vertices. The algorithms use the technique of *low-treewidth pattern covering,* introduced in the paper above;

here we show how this strategy can be made to work for graphs with polynomial growth.

Formally, we prove that, given a graph \(G\) of polynomial growth with growth rate \(d\) and an integer \(k\), one can in randomized polynomial time find a subset

\(A \subseteq V(G)\) such that on one hand the treewidth of \(G[A]\) is \(\mathcal{O}(k^{1-\frac{1}{1+d}} \log k)\), and on the other hand for every set \(X \subseteq V(G)\) of size at most \(k\), the probability that \(X \subseteq A\) is \(2^{-\mathcal{O}(k^{1-\frac{1}{1+d}} \log^2 k)}\). Together with standard dynamic programming techniques on graphs of bounded treewidth, this statement gives subexponential parameterized algorithms for a number of subgraph search problems, such as Long Path or Steiner Tree, in graphs of polynomial growth.

We complement the algorithm with an almost tight lower bound for \textsc{Long Path}: unless the Exponential Time Hypothesis fails, no parameterized algorithm with running time \(2^{k^{1-\frac{1}{d}-\varepsilon}}n^{\mathcal{O}(1)}\) is possible for any \(\varepsilon > 0\) and any integer \(d \geq 3\).

**Excluding hooks and their complements**

The celebrated Erdos-Hajnal conjecture states that for every \(n\)-vertex undirected graph \(H\) there exists \(\varepsilon(H)>0\) such that every graph \(G\) that does not contain \(H\) as an induced subgraph contains a clique or an independent set of size at least \(n^{\varepsilon(H)}\). A weaker version of the conjecture states that the polynomial-size clique/independent set phenomenon occurs if one excludes both \(H\) and its complement \(H^c\). We show that the weaker conjecture holds if \(H\) is any path with a pendant edge at its third vertex; thus we give a new infinite family of graphs for which the conjecture holds. Along the way we prove that the Erdos-Hajnal conjecture holds for a few new hereditary graph classes including claw-free perfect graphs and line graphs.