#### Conference papers

**On subexponential parameterized algorithms for Steiner Tree and Directed Subset TSP on planar graphs**preprint*, accepted at FOCS 2018*

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.

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

**Multi-budgeted Cuts**

*accepted at IPEC 2018*

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.

8. Shaohua Li, Marcin Pilipczuk

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

preprint*, accepted at WG 2018*

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.

7. 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

5. 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.

4. 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.