Search

For a fixed integer $t \geq 1$, a ($t$-)long claw, denoted $S_{t,t,t}$, is the unique tree with three leaves, each at distance exactly $t$ from the vertex of degree three. Majewski et al. [ICALP 2022, ACM ToCT 2024] proved an analog of the Gy\'{a}rf\'{a}s' path argument for $S_{t,t,t}$-free graphs: given an $n$-vertex $S_{t,t,t}$-free graph, one can delete neighborhoods of $\mathcal{O}(\log n)$ vertices so that the remainder admits an extended strip decomposition (an appropriate generalization of partition into connected components) into particles of multiplicatively smaller size. This statement has proven to be very useful in designing quasi-polynomial time algorithms for Maximum Weight Independent Set and related problems in $S_{t,t,t}$-free graphs. In this work, we refine the argument of Majewski et al. and show that a constant number of neighborhoods suffice.

A recent work of Abbasi et al. [FOCS 2023] introduced the notion of $\varepsilon$-scatter dimension of a metric space and showed a general framework for efficient parameterized approximation schemes (so-called EPASes) for a wide range of clustering problems in classes of metric spaces that admit a bound on the $\varepsilon$-scatter dimension. Our main result is such a bound for metrics induced by graphs from any fixed proper minor-closed graph class. The bound is double-exponential in $\varepsilon^{-1}$ and the Hadwiger number of the graph class and is accompanied by a nearly tight lower bound that holds even in graph classes of bounded treewidth. On the way to the main result, we introduce metric analogs of well-known graph invariants from the theory of sparsity, including generalized coloring numbers and flatness (aka uniform quasi-wideness), and show bounds for these invariants in proper minor-closed graph classes. Finally, we show the power of newly introduced toolbox by showing a coreset for $k$-Center in any proper minor-closed graph class whose size is polynomial in $k$ (but the exponent of the polynomial depends on the graph class and $\varepsilon^{-1}$)., Comment: Full version of a paper accepted to SODA 2025

In this note we show a polynomial bound on the number of minimal separators and potential maximal cliques in $P_6$-free graphs of bounded clique number.

We revisit the recent polynomial-time algorithm for the MAX WEIGHT INDEPENDENT SET (MWIS) problem in bounded-degree graphs that do not contain a fixed graph whose every component is a subdivided claw as an induced subgraph [Abrishami, Dibek, Chudnovsky, Rz\k{a}\.zewski, SODA 2022]. First, we show that with an arguably simpler approach we can obtain a faster algorithm with running time $n^{\mathcal{O}(\Delta^2)}$, where $n$ is the number of vertices of the instance and $\Delta$ is the maximum degree. Then we combine our technique with known results concerning tree decompositions and provide a polynomial-time algorithm for MWIS in graphs excluding a fixed graph whose every component is a subdivided claw as an induced subgraph, and a fixed biclique as a subgraph., Comment: arXiv admin note: text overlap with arXiv:2107.05434

We prove that a number of computational problems that ask for the largest sparse induced subgraph satisfying some property definable in CMSO2 logic, most notably Feedback Vertex Set, are polynomial-time solvable in the class of $P_6$-free graphs. This generalizes the work of Grzesik, Klimo\v{s}ov\'{a}, Pilipczuk, and Pilipczuk on the Maximum Weight Independent Set problem in $P_6$-free graphs~[SODA 2019, TALG 2022], and of Abrishami, Chudnovsky, Pilipczuk, Rz\k{a}\.zewski, and Seymour on problems in $P_5$-free graphs~[SODA~2021]. The key step is a new generalization of the framework of potential maximal cliques. We show that instead of listing a large family of potential maximal cliques, it is sufficient to only list their carvers: vertex sets that contain the same vertices from the sought solution and have similar separation properties.

We prove that there is a randomized polynomial-time algorithm that given an edge-weighted graph $G$ excluding a fixed-minor $Q$ on $n$ vertices and an accuracy parameter $\varepsilon>0$, constructs an edge-weighted graph~$H$ and an embedding $\eta\colon V(G)\to V(H)$ with the following properties: * For any constant size $Q$, the treewidth of $H$ is polynomial in $\varepsilon^{-1}$, $\log n$, and the logarithm of the stretch of the distance metric in $G$. * The expected multiplicative distortion is $(1+\varepsilon)$: for every pair of vertices $u,v$ of $G$, we have $\mathrm{dist}_H(\eta(u),\eta(v))\geq \mathrm{dist}_G(u,v)$ always and $\mathrm{Exp}[\mathrm{dist}_H(\eta(u),\eta(v))]\leq (1+\varepsilon)\mathrm{dist}_G(u,v)$. Our embedding is the first to achieve polylogarithmic treewidth of the host graph and comes close to the lower bound by Carroll and Goel, who showed that any embedding of a planar graph with $\mathcal{O}(1)$ expected distortion requires the host graph to have treewidth $\Omega(\log n)$. It also provides a unified framework for obtaining randomized quasi-polynomial-time approximation schemes for a variety of problems including network design, clustering or routing problems, in minor-free metrics where the optimization goal is the sum of selected distances. Applications include the capacitated vehicle routing problem, and capacitated clustering problems.

We show that every graph with pathwidth strictly less than $a$ that contains no path on $2^b$ vertices as a subgraph has treedepth at most $10ab$. The bound is best possible up to a constant factor., Comment: v3: corrected some typos. v2: revised following referees' comments, corrects an error in v1

We prove that Graph Isomorphism and Canonization in graphs excluding a fixed graph $H$ as a minor can be solved by an algorithm working in time $f(H)\cdot n^{O(1)}$, where $f$ is some function. In other words, we show that these problems are fixed-parameter tractable when parameterized by the size of the excluded minor, with the caveat that the bound on the running time is not necessarily computable. The underlying approach is based on decomposing the graph in a canonical way into unbreakable (intuitively, well-connected) parts, which essentially provides a reduction to the case where the given $H$-minor-free graph is unbreakable itself. This is complemented by an analysis of unbreakable $H$-minor-free graphs, performed in a second subordinate manuscript, which reveals that every such graph can be canonically decomposed into a part that admits few automorphisms and a part that has bounded treewidth., Comment: Part I of a full version of a paper accepted at STOC 2022

A set $X \subseteq V(G)$ in a graph $G$ is $(q,k)$-unbreakable if every separation $(A,B)$ of order at most $k$ in $G$ satisfies $|A \cap X| \leq q$ or $|B \cap X| \leq q$. In this paper, we prove the following result: If a graph $G$ excludes a fixed complete graph $K_h$ as a minor and satisfies certain unbreakability guarantees, then $G$ is almost rigid in the following sense: the vertices of $G$ can be partitioned in an isomorphism-invariant way into a part inducing a graph of bounded treewidth and a part that admits a small isomorphism-invariant family of labelings. This result is the key ingredient in the fixed-parameter algorithm for Graph Isomorphism parameterized by the Hadwiger number of the graph, which is presented in a companion paper., Comment: Part II of a full version of a paper appearing at STOC 2022

An oriented graph is a digraph that does not contain a directed cycle of length two. An (oriented) graph $D$ is $H$-free if $D$ does not contain $H$ as an induced sub(di)graph. The Gy\'arf\'as-Sumner conjecture is a widely-open conjecture on simple graphs, which states that for any forest $F$, there is some function $f$ such that every $F$-free graph $G$ with clique number $\omega(G)$ has chromatic number at most $f(\omega(G))$. Aboulker, Charbit, and Naserasr [Extension of Gy\'arf\'as-Sumner Conjecture to Digraphs; E-JC 2021] proposed an analogue of this conjecture to the dichromatic number of oriented graphs. The dichromatic number of a digraph $D$ is the minimum number of colors required to color the vertex set of $D$ so that no directed cycle in $D$ is monochromatic. Aboulker, Charbit, and Naserasr's $\overrightarrow{\chi}$-boundedness conjecture states that for every oriented forest $F$, there is some function $f$ such that every $F$-free oriented graph $D$ has dichromatic number at most $f(\omega(D))$, where $\omega(D)$ is the size of a maximum clique in the graph underlying $D$. In this paper, we perform the first step towards proving Aboulker, Charbit, and Naserasr's $\overrightarrow{\chi}$-boundedness conjecture by showing that it holds when $F$ is any orientation of a path on four vertices., Comment: 24 pages, 5 figures

We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class $\mathcal{G}$ there exists a constant $k$ such that no member of $\mathcal{G}$ contains a $k$-creature as an induced subgraph or a $k$-skinny-ladder as an induced minor, then there exists a polynomial $p$ such that every $G \in \mathcal{G}$ contains at most $p(|V(G)|)$ minimal separators. By a result of Fomin, Todinca, and Villanger [SIAM J. Comput. 2015] the latter entails the existence of polynomial-time algorithms for Maximum Weight Independent Set, Feedback Vertex Set and many other problems, when restricted to an input graph from $\mathcal{G}$. Furthermore, as shown by Gartland and Lokshtanov, our result implies a full dichotomy of hereditary graph classes defined by a finite set of forbidden induced subgraphs into tame (admitting a polynomial bound of the number of minimal separators) and feral (containing infinitely many graphs with exponential number of minimal separators).

We revisit recent developments for the Maximum Weight Independent Set problem in graphs excluding a subdivided claw $S_{t,t,t}$ as an induced subgraph [Chudnovsky, Pilipczuk, Pilipczuk, Thomass\'{e}, SODA 2020] and provide a subexponential-time algorithm with improved running time $2^{\mathcal{O}(\sqrt{n}\log n)}$ and a quasipolynomial-time approximation scheme with improved running time $2^{\mathcal{O}(\varepsilon^{-1} \log^{5} n)}$. The Gy\'arf\'as' path argument, a powerful tool that is the main building block for many algorithms in $P_t$-free graphs, ensures that given an $n$-vertex $P_t$-free graph, in polynomial time we can find a set $P$ of at most $t-1$ vertices, such that every connected component of $G-N[P]$ has at most $n/2$ vertices. Our main technical contribution is an analog of this result for $S_{t,t,t}$-free graphs: given an $n$-vertex $S_{t,t,t}$-free graph, in polynomial time we can find a set $P$ of $\mathcal{O}(t \log n)$ vertices and an extended strip decomposition (an appropriate analog of the decomposition into connected components) of $G-N[P]$ such that every particle (an appropriate analog of a connected component to recurse on) of the said extended strip decomposition has at most $n/2$ vertices., Comment: 19 pages, 2 figures

Twin-width is a newly introduced graph width parameter that aims at generalizing a wide range of "nicely structured" graph classes. In this work, we focus on obtaining good bounds on twin-width $\text{tww}(G)$ for graphs $G$ from a number of classic graph classes. We prove the following: - $\text{tww}(G) \leq 3\cdot 2^{\text{tw}(G)-1}$, where $\text{tw}(G)$ is the treewidth of $G$, - $\text{tww}(G) \leq \max(4\text{bw}(G),\frac{9}{2}\text{bw}(G)-3)$ for a planar graph $G$ with $\text{bw}(G) \geq 2$, where $\text{bw}(G)$ is the branchwidth of $G$, - $\text{tww}(G) \leq 183$ for a planar graph $G$, - the twin-width of a universal bipartite graph $(X,2^X,E)$ with $|X|=n$ is $n - \log_2(n) + \mathcal{O}(1)$ . An important idea behind the bounds for planar graphs is to use an embedding of the graph and sphere-cut decompositions to obtain good bounds on neighbourhood complexity., Comment: 13 pages, 2 figures

We show a flow-augmentation algorithm in directed graphs: There exists a randomized polynomial-time algorithm that, given a directed graph $G$, two vertices $s,t \in V(G)$, and an integer $k$, adds (randomly) to $G$ a number of arcs such that for every minimal $st$-cut $Z$ in $G$ of size at most $k$, with probability $2^{-\mathrm{poly}(k)}$ the set $Z$ becomes a minimum $st$-cut in the resulting graph. We also provide a deterministic counterpart of this procedure. The directed flow-augmentation tool allows us to prove fixed-parameter tractability of a number of problems parameterized by the cardinality of the deletion set, whose parameterized complexity status was repeatedly posed as open problems: (1) Chain SAT, defined by Chitnis, Egri, and Marx [ESA'13, Algorithmica'17], (2) a number of weighted variants of classic directed cut problems, such as Weighted $st$-Cut} or Weighted Directed Feedback Vertex Set. By proving that Chain SAT is FPT, we confirm a conjecture of Chitnis, Egri, and Marx that, for any graph $H$, if the List $H$-Coloring problem is polynomial-time solvable, then the corresponding vertex-deletion problem is fixed-parameter tractable., Comment: v2. Major update of three flow-augmentation papers. Includes a deterministic version. Weighted Almost 2-SAT algorithm has been removed, as it is superseded by a more general algorithm of Flow-Augmentation III (arXiv:2207.07422)

At IPEC 2020, Bergougnoux, Bonnet, Brettell, and Kwon showed that a number of problems related to the classic Feedback Vertex Set (FVS) problem do not admit a $2^{o(k \log k)} \cdot n^{\mathcal{O}(1)}$-time algorithm on graphs of treewidth at most $k$, assuming the Exponential Time Hypothesis. This contrasts with the $3^{k} \cdot k^{\mathcal{O}(1)} \cdot n$-time algorithm for FVS using the Cut&Count technique. During their live talk at IPEC 2020, Bergougnoux et al.~posed a number of open questions, which we answer in this work. - Subset Even Cycle Transversal, Subset Odd Cycle Transversal, Subset Feedback Vertex Set can be solved in time $2^{\mathcal{O}(k \log k)} \cdot n$ in graphs of treewidth at most $k$. This matches a lower bound for Even Cycle Transversal of Bergougnoux et al.~and improves the polynomial factor in some of their upper bounds. - Subset Feedback Vertex Set and Node Multiway Cut can be solved in time $2^{\mathcal{O}(k \log k)} \cdot n$, if the input graph is given as a clique-width expression of size $n$ and width $k$. - Odd Cycle Transversal can be solved in time $4^k \cdot k^{\mathcal{O}(1)} \cdot n$ if the input graph is given as a clique-width expression of size $n$ and width $k$. Furthermore, the existence of a constant $\varepsilon > 0$ and an algorithm performing this task in time $(4-\varepsilon)^k \cdot n^{\mathcal{O}(1)}$ would contradict the Strong Exponential Time Hypothesis., Comment: 32 pages, 4 figures

The Directed Grid Theorem, stating that there is a function $f$ such that a directed graphs of directed treewidth at least $f(k)$ contains a directed grid of size at least $k$ as a butterfly minor, after being a conjecture for nearly 20 years, has been proven in 2015 by Kawarabayashi and Kreutzer. However, the function $f$ obtained in the proof is very fast growing. In this work, we show that if one relaxes directed grid to bramble of constant congestion, one can obtain a polynomial bound. More precisely, we show that for every $k \geq 1$ there exists $t = \mathcal{O}(k^{48} \log^{13} k)$ such that every directed graph of directed treewidth at least $t$ contains a bramble of congestion at most $8$ and size at least $k$., Comment: 16 pages, 5 figures

The Metric Dimension problem asks for a minimum-sized resolving set in a given (unweighted, undirected) graph $G$. Here, a set $S \subseteq V(G)$ is resolving if no two distinct vertices of $G$ have the same distance vector to $S$. The complexity of Metric Dimension in graphs of bounded treewidth remained elusive in the past years. Recently, Bonnet and Purohit [IPEC 2019] showed that the problem is W[1]-hard under treewidth parameterization. In this work, we strengthen their lower bound to show that Metric Dimension is NP-hard in graphs of treewidth 24.

In a recent breakthrough work, Gartland and Lokshtanov [FOCS 2020] showed a quasi-polynomial-time algorithm for Maximum Weight Independent Set in $P_t$-free graphs, that is, graphs excluding a fixed path as an induced subgraph. Their algorithm runs in time $n^{\mathcal{O}(\log^3 n)}$, where $t$ is assumed to be a constant. Inspired by their ideas, we present an arguably simpler algorithm with an improved running time bound of $n^{\mathcal{O}(\log^2 n)}$. Our main insight is that a connected $P_t$-free graph always contains a vertex $w$ whose neighborhood intersects, for a constant fraction of pairs $\{u,v\} \in \binom{V(G)}{2}$, a constant fraction of induced $u-v$ paths. Since a $P_t$-free graph contains $\mathcal{O}(n^{t-1})$ induced paths in total, branching on such a vertex and recursing independently on the connected components leads to a quasi-polynomial running time bound. We also show that the same approach can be used to obtain quasi-polynomial-time algorithms for related problems, including Maximum Weight Induced Matching and 3-Coloring., Comment: Paper accepted to SOSA 2021. The results on $C_{>t}$-free graphs from v1 were moved to arXiv:2007.11402

A bramble in an undirected graph $G$ is a family of connected subgraphs of $G$ such that for every two subgraphs $H_1$ and $H_2$ in the bramble either $V(H_1) \cap V(H_2) \neq \emptyset$ or there is an edge of $G$ with one endpoint in $V(H_1)$ and the second endpoint in $V(H_2)$. The order of the bramble is the minimum size of a vertex set that intersects all elements of a bramble. Brambles are objects dual to treewidth: As shown by Seymour and Thomas, the maximum order of a bramble in an undirected graph $G$ equals one plus the treewidth of $G$. However, as shown by Grohe and Marx, brambles of high order may necessarily be of exponential size: In a constant-degree $n$-vertex expander a bramble of order $\Omega(n^{1/2+\delta})$ requires size exponential in $\Omega(n^{2\delta})$ for any fixed $\delta \in (0,\frac{1}{2}]$. On the other hand, the combination of results of Grohe and Marx and Chekuri and Chuzhoy shows that a graph of treewidth $k$ admits a bramble of order $\widetilde{\Omega}(k^{1/2})$ and size $\widetilde{\mathcal{O}}(k^{3/2})$. ($\widetilde{\Omega}$ and $\widetilde{\mathcal{O}}$ hide polylogarithmic factors and divisors, respectively.) In this note, we first sharpen the second bound by proving that every graph $G$ of treewidth at least $k$ contains a bramble of order $\widetilde{\Omega}(k^{1/2})$ and congestion $2$, i.e., every vertex of $G$ is contained in at most two elements of the bramble (thus the bramble is of size linear in its order). Second, we provide a tight upper bound for the lower bound of Grohe and Marx: For every $\delta \in (0,\frac{1}{2}]$, every graph $G$ of treewidth at least $k$ contains a bramble of order $\widetilde{\Omega}(k^{1/2+\delta})$ and size $2^{\widetilde{\mathcal{O}}(k^{2\delta})}$.

Given a graph $G$ and an integer $p$, a coloring $f : V(G) \to \mathbb{N}$ is \emph{$p$-centered} if for every connected subgraph $H$ of $G$, either $f$ uses more than $p$ colors on $H$ or there is a color that appears exactly once in $H$. The notion of $p$-centered colorings plays a central role in the theory of sparse graphs. In this note we show two lower bounds on the number of colors required in a $p$-centered coloring. First, we consider monotone classes of graphs whose shallow minors have average degree bounded polynomially in the radius, or equivalently (by a result of Dvo\v{r}\'ak and Norin), admitting strongly sublinear separators. We construct such a class such that $p$-centered colorings require a number of colors super-polynomial in $p$. This is in contrast with a recent result of Pilipczuk and Siebertz, who established a polynomial upper bound in the special case of graphs excluding a fixed minor. Second, we consider graphs of maximum degree $\Delta$. D\k{e}bski, Felsner, Micek, and Schr\"{o}der recently proved that these graphs have $p$-centered colorings with $O(\Delta^{2-1/p} p)$ colors. We show that there are graphs of maximum degree $\Delta$ that require $\Omega(\Delta^{2-1/p} p \ln^{-1/p}\Delta)$ colors in any $p$-centered coloring, thus matching their upper bound up to a logarithmic factor., Comment: v3: final version with journal layout v2: revised following referees' comments

We present a data structure that in a dynamic graph of treedepth at most $d$, which is modified over time by edge insertions and deletions, maintains an optimum-height elimination forest. The data structure achieves worst-case update time $2^{{\cal O}(d^2)}$, which matches the best known parameter dependency in the running time of a static fpt algorithm for computing the treedepth of a graph. This improves a result of Dvo\v{r}\'ak et al. [ESA 2014], who for the same problem achieved update time $f(d)$ for some non-elementary (i.e. tower-exponential) function $f$. As a by-product, we improve known upper bounds on the sizes of minimal obstructions for having treedepth $d$ from doubly-exponential in $d$ to $d^{{\cal O}(d)}$. As applications, we design new fully dynamic parameterized data structures for detecting long paths and cycles in general graphs. More precisely, for a fixed parameter $k$ and a dynamic graph $G$, modified over time by edge insertions and deletions, our data structures maintain answers to the following queries: - Does $G$ contain a simple path on $k$ vertices? - Does $G$ contain a simple cycle on at least $k$ vertices? In the first case, the data structure achieves amortized update time $2^{{\cal O}(k^2)}$. In the second case, the amortized update time is $2^{{\cal O}(k^4)} + {\cal O}(k \log n)$. In both cases we assume access to a dictionary on the edges of $G$., Comment: 74 pages, 5 figures

A graph is called $P_t$-free} if it does not contain a $t$-vertex path as an induced subgraph. While $P_4$-free graphs are exactly cographs, the structure of $P_t$-free graphs for $t \geq 5$ remains little understood. On one hand, classic computational problems such as Maximum Weight Independent Set (MWIS) and $3$-Coloring are not known to be NP-hard on $P_t$-free graphs for any fixed $t$. On the other hand, despite significant effort, polynomial-time algorithms for MWIS in $P_6$-free graphs~[SODA 2019] and $3$-Coloring in $P_7$-free graphs~[Combinatorica 2018] have been found only recently. In both cases, the algorithms rely on deep structural insights into the considered graph classes. One of the main tools in the algorithms for MWIS in $P_5$-free graphs~[SODA 2014] and in $P_6$-free graphs~[SODA 2019] is the so-called Separator Covering Lemma that asserts that every minimal separator in the graph can be covered by the union of neighborhoods of a constant number of vertices. In this note we show that such a statement generalizes to $P_7$-free graphs and is false in $P_8$-free graphs. We also discuss analogues of such a statement for covering potential maximal cliques with unions of neighborhoods.

A hole in a graph is an induced cycle of length at least 4. A hole is long if its length is at least 5. By $P_t$ we denote a path on $t$ vertices. In this paper we give polynomial-time algorithms for the following problems: the Maximum Weight Independent Set problem in long-hole-free graphs, and the Feedback Vertex Set problem in $P_5$-free graphs. Each of the above results resolves a corresponding long-standing open problem. An extended $C_5$ is a five-vertex hole with an additional vertex adjacent to one or two consecutive vertices of the hole. Let $\mathcal{C}$ be the class of graphs excluding an extended $C_5$ and holes of length at least $6$ as induced subgraphs; $\mathcal{C}$ contains all long-hole-free graphs and all $P_5$-free graphs. We show that, given an $n$-vertex graph $G \in \mathcal{C}$ with vertex weights and an integer $k$, one can in time $n^{\Oh(k)}$ find a maximum-weight induced subgraph of $G$ of treewidth less than $k$. This implies both aforementioned results.

Given two disjoint sets $W_1$ and $W_2$ of points in the plane, the Optimal Discretization problem asks for the minimum size of a family of horizontal and vertical lines that separate $W_1$ from $W_2$, that is, in every region into which the lines partition the plane there are either only points of $W_1$, or only points of $W_2$, or the region is empty. Equivalently, Optimal Discretization can be phrased as a task of discretizing continuous variables: we would like to discretize the range of $x$-coordinates and the range of $y$-coordinates into as few segments as possible, maintaining that no pair of points from $W_1 \times W_2$ are projected onto the same pair of segments under this discretization. We provide a fixed-parameter algorithm for the problem, parameterized by the number of lines in the solution. Our algorithm works in time $2^{O(k^2 \log k)} n^{O(1)}$, where $k$ is the bound on the number of lines to find and $n$ is the number of points in the input. Our result answers in positive a question of Bonnet, Giannopolous, and Lampis [IPEC 2017] and of Froese (PhD thesis, 2018) and is in contrast with the known intractability of two closely related generalizations: the Rectangle Stabbing problem and the generalization in which the selected lines are not required to be axis-parallel., Comment: Accepted to ACM-SIAM Symposium on Discrete Algorithms (SODA 2021). 53 pages, 18 figures

In the (binary) Distinct Vectors problem we are given a binary matrix A with pairwise different rows and want to select at most k columns such that, restricting the matrix to these columns, all rows are still pairwise different. A result by Froese et al. [JCSS] implies a 2^2^(O(k)) * poly(|A|)-time brute-force algorithm for Distinct Vectors. We show that this running time bound is essentially optimal by showing that there is a constant c such that the existence of an algorithm solving Distinct Vectors with running time 2^(O(2^(ck))) * poly(|A|) would contradict the Exponential Time Hypothesis.

A {\em theta} is a graph made of three internally vertex-disjoint chordless paths $P_1 = a \dots b$, $P_2 = a \dots b$, $P_3 = a \dots b$ of length at least~2 and such that no edges exist between the paths except the three edges incident to $a$ and the three edges incident to $b$. A {\em pyramid} is a graph made of three chordless paths $P_1 = a \dots b_1$, $P_2 = a \dots b_2$, $P_3 = a \dots b_3$ of length at least~1, two of which have length at least 2, vertex-disjoint except at $a$, and such that $b_1b_2b_3$ is a triangle and no edges exist between the paths except those of the triangle and the three edges incident to~$a$. An \emph{even hole} is a chordless cycle of even length. For three non-negative integers $i\leq j\leq k$, let $S_{i,j,k}$ be the tree with a vertex $v$, from which start three paths with $i$, $j$, and $k$ edges respectively. We denote by $K_t$ the complete graph on $t$ vertices. We prove that for all non-negative integers $i, j, k$, the class of graphs that contain no theta, no $K_3$, and no $S_{i, j, k}$ as induced subgraphs have bounded treewidth. We prove that for all non-negative integers $i, j, k, t$, the class of graphs that contain no even hole, no pyramid, no $K_t$, and no $S_{i, j, k}$ as induced subgraphs have bounded treewidth. To bound the treewidth, we prove that every graph of large treewidth must contain a large clique or a minimal separator of large cardinality.

We confirm Jones' Conjecture for subcubic graphs. Namely, if a subcubic planar graph does not contain $k+1$ vertex-disjoint cycles, then it suffices to delete $2k$ vertices to obtain a forest.

Given a graph $G=(V,E)$ and an integer $k$, the Cluster Editing problem asks whether we can transform $G$ into a union of vertex-disjoint cliques by at most $k$ modifications (edge deletions or insertions). In this paper, we study the following variant of Cluster Editing. We are given a graph $G=(V,E)$, a packing $\cal H$ of modification-disjoint induced $P_3$s (no pair of $P_3$s in $\cal H$ share an edge or non-edge) and an integer $\ell$. The task is to decide whether $G$ can be transformed into a union of vertex-disjoint cliques by at most $\ell+|\cal H|$ modifications (edge deletions or insertions). We show that this problem is NP-hard even when $\ell=0$ (in which case the problem asks to turn $G$ into a disjoint union of cliques by performing exactly one edge deletion or insertion per element of $\cal H$) and when each vertex is in at most 23 $P_3$s of the packing. This answers negatively a question of van Bevern, Froese, and Komusiewicz (CSR 2016, ToCS 2018), repeated by C. Komusiewicz at Shonan meeting no. 144 in March 2019. We then initiate the study to find the largest integer $c$ such that the problem remains tractable when restricting to packings such that each vertex is in at most $c$ packed $P_3$s. Here packed $P_3$s are those belonging to the packing $\cal H$. Van Bevern et al. showed that the case $c = 1$ is fixed-parameter tractable with respect to $\ell$ and we show that the case $c = 2$ is solvable in $|V|^{2\ell + O(1)}$ time., Comment: 41 pages, 13 figures

In the Maximum Independent Set problem we are asked to find a set of pairwise nonadjacent vertices in a given graph with the maximum possible cardinality. In general graphs, this classical problem is known to be NP-hard and hard to approximate within a factor of $n^{1-\varepsilon}$ for any $\varepsilon > 0$. Due to this, investigating the complexity of Maximum Independent Set in various graph classes in hope of finding better tractability results is an active research direction. In $H$-free graphs, that is, graphs not containing a fixed graph $H$ as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever $H$ contains a cycle, a vertex of degree at least four, or two vertices of degree at least three in one connected component. For the remaining cases, where every component of $H$ is a path or a subdivided claw, the complexity of Maximum Independent Set remains widely open, with only a handful of polynomial-time solvability results for small graphs $H$ such as $P_5$, $P_6$, the claw, or the fork. We show that for every graph $H$ for which Maximum Independent Set is not known to be APX-hard and SUBEXP-hard in $H$-free graphs, the problem admits a quasi-polynomial time approximation scheme and a subexponential-time exact algorithm in this graph class. Our algorithm works also in the more general weighted setting, where the input graph is supplied with a weight function on vertices and we are maximizing the total weight of an independent set., Comment: v2: added results on subexponential algorithms, v3: revision after reviewers' remarks, v4: final version accepted at SICOMP

The celebrated Erd\H{o}s-P\'osa theorem states that every undirected graph that does not admit a family of $k$ vertex-disjoint cycles contains a feedback vertex set (a set of vertices hitting all cycles in the graph) of size $O(k \log k)$. After being known for long as Younger's conjecture, a similar statement for directed graphs has been proven in 1996 by Reed, Robertson, Seymour, and Thomas. However, in their proof, the dependency of the size of the feedback vertex set on the size of vertex-disjoint cycle packing is not elementary. We show that if we compare the size of a minimum feedback vertex set in a directed graph with the quarter-integral cycle packing number, we obtain a polynomial bound. More precisely, we show that if in a directed graph $G$ there is no family of $k$ cycles such that every vertex of $G$ is in at most four of the cycles, then there exists a feedback vertex set in $G$ of size $O(k^4)$. Furthermore, a variant of our proof shows that if in a directed graph $G$ there is no family of $k$ cycles such that every vertex of $G$ is in at most two of the cycles, then there exists a feedback vertex set in $G$ of size $O(k^6)$. On the way there we prove a more general result about quarter-integral packing of subgraphs of high directed treewidth: for every pair of positive integers $a$ and $b$, if a directed graph $G$ has directed treewidth $\Omega(a^6 b^8 \log^2(ab))$, then one can find in $G$ a family of $a$ subgraphs, each of directed treewidth at least $b$, such that every vertex of $G$ is in at most four subgraphs., Comment: Accepted to European Symposium on Algorithms (ESA '19)

Treedepth, a more restrictive graph width parameter than treewidth and pathwidth, plays a major role in the theory of sparse graph classes. We show that there exists a constant $C$ such that for every positive integers $a,b$ and a graph $G$, if the treedepth of $G$ is at least $Cab$, then the treewidth of $G$ is at least $a$ or $G$ contains a subcubic (i.e., of maximum degree at most $3$) tree of treedepth at least $b$ as a subgraph. As a direct corollary, we obtain that every graph of treedepth $\Omega(k^3)$ is either of treewidth at least $k$, contains a subdivision of full binary tree of depth $k$, or contains a path of length $2^k$. This improves the bound of $\Omega(k^5 \log^2 k)$ of Kawarabayashi and Rossman [SODA 2018]. We also show an application of our techniques for approximation algorithms of treedepth: given a graph $G$ of treedepth $k$ and treewidth $t$, one can in polynomial time compute a treedepth decomposition of $G$ of width $\mathcal{O}(kt \log^{3/2} t)$. This improves upon a bound of $\mathcal{O}(kt^2 \log t)$ stemming from a tradeoff between known results. The main technical ingredient in our result is a proof that every tree of treedepth $d$ contains a subcubic subtree of treedepth at least $d \cdot \log_3 ((1+\sqrt{5})/2)$.

A hole in a graph is an induced cycle of length at least $4$, and an antihole is the complement of an induced cycle of length at least $4$. A hole or antihole is long if its length is at least $5$. For an integer $k$, the $k$-prism is the graph consisting of two cliques of size $k$ joined by a matching. The complexity of Maximum (Weight) Independent Set (MWIS) in long-hole-free graphs remains an important open problem. In this paper we give a polynomial time algorithm to solve MWIS in long-hole-free graphs with no $k$-prism (for any fixed integer $k$), and a subexponential algorithm for MWIS in long-hole-free graphs in general. As a special case this gives a polynomial time algorithm to find a maximum weight clique in perfect graphs with no long antihole, and no hole of length $6$. The algorithms use the framework of minimal chordal completions and potential maximal cliques.

Let $T$ be a tree such that all its vertices of degree more than two lie on one path, that is, $T$ is a caterpillar subdivision. We prove that there exists $\epsilon>0$ such that for every graph $G$ with $|V(G)|\ge 2$ not containing $T$ as an induced subgraph, either some vertex has at least $\epsilon|V(G)|$ neighbours, or there are two disjoint sets of vertices $A,B$, both of cardinality at least $\epsilon|V(G)|$, where there is no edge joining $A$ and $B$. A consequence is: for every caterpillar subdivision $T$, there exists $c>0$ such that for every graph $G$ containing neither of $T$ and its complement as an induced subgraph, $G$ has a clique or stable set with at least $|V(G)|^c$ vertices. This extends a theorem of Bousquet, Lagoutte and Thomass\'e [JCTB 2015], who proved the same when $T$ is a path, and a recent theorem of Choromanski, Falik, Liebenau, Patel and Pilipczuk [Electron. J. Combin. 2018], who proved it when $T$ is a "hook".

The notions of bounded expansion and nowhere denseness not only offer robust and general definitions of uniform sparseness of graphs, they also describe the tractability boundary for several important algorithmic questions. In this paper we study two structural properties of these graph classes that are of particular importance in this context, namely the property of having bounded generalized coloring numbers and the property of being uniformly quasi-wide. We provide experimental evaluations of several algorithms that approximate these parameters on real-world graphs. On the theoretical side, we provide a new algorithm for uniform quasi-wideness with polynomial size guarantees in graph classes of bounded expansion and show a lower bound indicating that the guarantees of this algorithm are close to optimal in graph classes with fixed excluded minor., Comment: Full version of a paper that appeared at SEA 2018

The celebrated Erd\H{o}s-Hajnal conjecture states that for every proper hereditary graph class $\mathcal{G}$ there exists a constant $\varepsilon = \varepsilon(\mathcal{G}) > 0$ such that every graph $G \in \mathcal{G}$ contains a clique or an independent set of size $|V(G)|^\varepsilon$. Recently, there has been a growing interest in the symmetrized variant of this conjecture, where one additionally requires $\mathcal{G}$ to be closed under complementation. We show that any hereditary graph class that is closed under complementation and excludes a fixed caterpillar as an induced subgraph satisfies the Erd\H{o}s-Hajnal conjecture. Here, a caterpillar is a tree whose vertices of degree at least three lie on a single path (i.e., our caterpillars may have arbitrarily long legs). In fact, we prove a stronger property of such graph classes, called in the literature the strong Erd\H{o}s-Hajnal property: for every such graph class $\mathcal{G}$, there exists a constant $\delta = \delta(\mathcal{G}) > 0$ such that every graph $G \in \mathcal{G}$ contains two disjoint sets $A,B \subseteq V(G)$ of size at least $\delta|V(G)|$ each so that either all edges between $A$ and $B$ are present in $G$, or none of them. This result significantly extends the family of graph classes for which we know that the strong Erd\H{o}s-Hajnal property holds; for graph classes excluding a graph $H$ and its complement it was previously known only for paths [Bousquet, Lagoutte, Thomass\'{e}, JCTB 2015] and hooks (i.e., paths with an additional pendant vertex at third vertex of the path) [Choromanski, Falik, Liebenau, Patel, Pilipczuk, arXiv:1508.00634].

In the classic Maximum Weight Independent Set problem we are given a graph $G$ with a nonnegative weight function on vertices, and the goal is to find an independent set in $G$ of maximum possible weight. While the problem is NP-hard in general, we give a polynomial-time algorithm working on any $P_6$-free graph, that is, a graph that has no path on $6$ vertices as an induced subgraph. This improves the polynomial-time algorithm on $P_5$-free graphs of Lokshtanov et al. (SODA 2014), and the quasipolynomial-time algorithm on $P_6$-free graphs of Lokshtanov et al (SODA 2016). The main technical contribution leading to our main result is enumeration of a polynomial-size family $\mathcal{F}$ of vertex subsets with the following property: for every maximal independent set $I$ in the graph, $\mathcal{F}$ contains all maximal cliques of some minimal chordal completion of $G$ that does not add any edge incident to a vertex of $I$.

Given a graph G and k pairs of vertices (s_1,t_1), ..., (s_k,t_k), the k-Vertex-Disjoint Paths problem asks for pairwise vertex-disjoint paths P_1, ..., P_k such that P_i goes from s_i to t_i. Schrijver [SICOMP'94] proved that the k-Vertex-Disjoint Paths problem on planar directed graphs can be solved in time n^{O(k)}. We give an algorithm with running time 2^{2^{O(k^2)}} n^{O(1)} for the problem, that is, we show the fixed-parameter tractability of the problem., Comment: 110 pages, 43 figures

In the EDGE CLIQUE COVER (ECC) problem, given a graph G and an integer k, we ask whether the edges of G can be covered with k complete subgraphs of G or, equivalently, whether G admits an intersection model on k-element universe. Gramm et al. [JEA 2008] have shown a set of simple rules that reduce the number of vertices of G to 2^k, and no algorithm is known with significantly better running time bound than a brute-force search on this reduced instance. In this paper we show that the approach of Gramm et al. is essentially optimal: we present a polynomial time algorithm that reduces an arbitrary 3-CNF-SAT formula with n variables and m clauses to an equivalent ECC instance (G,k) with k = O(log n) and |V(G)| = O(n + m). Consequently, there is no 2^{2^{o(k)}}poly(n) time algorithm for the ECC problem, unless the Exponential Time Hypothesis fails. To the best of our knowledge, these are the first results for a natural, fixed-parameter tractable problem, and proving that a doubly-exponential dependency on the parameter is essentially necessary., Comment: To appear in SODA 2013

Signed graphs, i.e., undirected graphs with edges labelled with a plus or minus sign, are commonly used to model relationships in social networks. Recently, Kermarrec and Thraves initiated the study of the problem of appropriately visualising the network: They asked whether any signed graph can be embedded into the metric space R^l in such a manner that every vertex is closer to all its friends (neighbours via positive edges) than to all its enemies (neighbours via negative edges). Interestingly, embeddability into R^1 can be expressed as a purely combinatorial problem. In this paper we pursue a deeper study of this particular case, answering several questions posed by Kermarrec and Thraves. First, we refine the approach of Kermarrec and Thraves for the case of complete signed graphs by showing that the problem is closely related to the recognition of proper interval graphs. Second, we prove that the general case, whose polynomial-time tractability remained open, is in fact NP-complete. Finally, we provide lower and upper bounds for the time complexity of the general case: we prove that the existence of a subexponential time (in the number of vertices and edges of the input signed graph) algorithm would violate the Exponential Time Hypothesis, whereas a simple dynamic programming approach gives a running time single-exponential in the number of vertices.

We study the parameterized complexity of the connected version of the vertex cover problem, where the solution set has to induce a connected subgraph. Although this problem does not admit a polynomial kernel for general graphs (unless NP is a subset of coNP/poly), for planar graphs Guo and Niedermeier [ICALP'08] showed a kernel with at most 14k vertices, subsequently improved by Wang et al. [MFCS'11] to 4k. The constant 4 here is so small that a natural question arises: could it be already an optimal value for this problem? In this paper we answer this quesion in negative: we show a (11/3)k-vertex kernel for Connected Vertex Cover in planar graphs. We believe that this result will motivate further study in search for an optimal kernel.

In this paper we provide algorithms faster than O*(2^n) for several NP-complete domination-type problems. More precisely, we provide: an algorithm for CAPACITATED DOMINATING SET that solves it in O(1.89^n), a branch-and-reduce algorithm solving LARGEST IRREDUNDANT SET in O(1.9657^n) time and a simple iterative-DFS algorithm for SMALLEST INCLUSION-MAXIMAL IRREDUNDANT SET that solves it in O(1.999956^n) time. We also provide an exponential approximation scheme for CAPACITATED DOMINATING SET. All algorithms require polynomial space. Despite the fact that the discussed problems are quite similar to the DOMINATING SET problem, we are not aware of any published algorithms solving these problems faster than the obvious O*(2^n) solution prior to this paper., Comment: Submitted to STACS 2010