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.