Search

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 ∈ 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−poly(k) the set Z becomes a minimumst-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: Chain SAT, defined by Chitnis, Egri, and Marx [ESA'13, Algorithmica'17], a number of weighted variants of classic directed cut problems, such as Weightedst-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 ListH-Coloring problem is polynomial-time solvable, then the corresponding vertex-deletion problem is fixed-parameter tractable. [ABSTRACT FROM AUTHOR]

We confirm a conjecture of Gartland and Lokshtanov [SODA 2023]: if for a hereditary graph class G there exists a constant k such that no member of 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 ∈ G contains at most p(|V(G)|) minimal separators. By a result of Fomin, Todinca, and Villanger [SIAM J. Comput., 44 (2015), pp. 54-87] 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 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). [ABSTRACT FROM AUTHOR]

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 Pt, 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 P5-free graphs. Each of the above results resolves a corresponding long-standing open problem. An extended C5 is a five-vertex hole with an additional vertex adjacent to one or two consecutive vertices of the hole. Let C be the class of graphs excluding an extended C5 and holes of length at least 6 as induced subgraphs; C contains all long-hole--free graphs and all P5-free graphs. We show that, given an n-vertex graph G\in C with vertex weights and an integer k, one can, in time, n\scrO (k) find a maximum-weight induced subgraph of G of treewidth less than k. This implies both aforementioned results. To achieve this goal, we extend the framework of potential maximal cliques (PMCs) to containers. Developed by Bouchitté and Todinca [SIAM J. Comput., 31 (2001), pp. 212--232] and extended by Fomin, Todinca, and Villanger [SIAM J. Comput., 44 (2015), pp. 54--87], this framework allows us to solve a wide variety of tasks, including finding a maximum-weight induced subgraph of treewidth less than k for fixed k, in time polynomial in the size of the graph and the number of potential maximal cliques. Further developments, tailored to solve the maximum weight independent set problem within this framework (e.g., for P5-free [Lokshtanov, Vatshelle, and Villanger, SODA 2014, pp. 570--581] or P6-free graphs [Grzesik, Klimo\v sov\'a, Pilipczuk, and Pilipczuk, ACM Trans. Algorithms, 18 (2022), pp. 4:1--4:57]), enumerate only a specifically chosen subset of all PMCs of a graph. In all aforementioned works, the final step is an involved dynamic programming algorithm whose state space is based on the considered list of PMCs. Here, we modify the dynamic programming algorithm and show that it is sufficient to consider only a container for each PMC: a superset of the maximal clique that intersects the sought solution only in the vertices of the PMC. This strengthening of the framework not only allows us to obtain our main result but also leads to significant simplifications of the reasoning in previous papers. [ABSTRACT FROM AUTHOR]

We present an undirected version of the recently introduced flow-augmentation technique: Given an undirected multigraph G with distinguished vertices s,t ∈ V(G) and an integer k, one can in randomized k(1) ⋅ (|V(G)| + |E(G)|) time sample a set A ⊆ \(\binom{V(G)}{2}\) such that the following holds: for every inclusion-wise minimal st-cut Z in G of cardinality at most k, Z becomes a minimum-cardinality cut between s and t in G+A (i.e., in the multigraph G with all edges of A added) with probability 2-(k log k). Compared to the version for directed graphs [STOC 2022], the version presented here has improved success probability (2-(k log k) instead of 2-(k4 log k)), linear dependency on the graph size in the running time bound, and an arguably simpler proof. An immediate corollary is that the Bi-objective st-Cut problem can be solved in randomized FPT time 2(k log k)(|V(G)|+|E(G)|) on undirected graphs. [ABSTRACT FROM AUTHOR]

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. [ABSTRACT FROM AUTHOR]

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 n1-ε for any ε> 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 P5, P6, the claw, or the fork. We prove that for every such "possibly tractable" graph H there exists an algorithm that, given an H-free graph G and an accuracy parameter ε> 0, finds an independent set in G of cardinality within a factor of (1 - ε) of the optimum in time exponential in a polynomial of log | V (G)| and ε-1. Furthermore, an independent set of maximum size can be found in subexponential time 2\scrO (| V (G)| 8/9| V (G)|). That is, 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 algorithms also work 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. [ABSTRACT FROM AUTHOR]

One of the first applications of the recently introduced technique of flow augmentation [Kim et al., STOC 2022] is a fixed-parameter algorithm for the weighted version of Directed Feedback Vertex Set, a landmark problem in parameterized complexity. In this article, we explore the applicability of flow augmentation to other weighted graph separation problems parameterized by the size of the cutset. We show the following: \bullet In weighted undirected graphs, Multicut is fixed-parameter tractable (FPT) in both the edge- and the vertex-deletion version. \bullet The weighted version of Group Feedback Vertex Set is FPT, even with oracle access to group operations. \bullet The weighted version of Directed Subset Feedback Vertex Set is FPT. Our study reveals Directed Symmetric Multicut as the next important graph separation problem whose parameterized complexity remains unknown, even in the unweighted setting. [ABSTRACT FROM AUTHOR]

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 ℋ of modification-disjoint induced P3s (no pair of P3s in ℋ share an edge or non-edge) and an integer ℓ. The task is to decide whether G can be transformed into a union of vertex-disjoint cliques by at most ℓ +|ℋ| modifications (edge deletions or insertions). We show that this problem is NP-hard even when ℓ = 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 ℋ) and when each vertex is in at most 23 P3s 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 P3s. Here packed P3s are those belonging to the packing ℋ. Van Bevern et al. showed that the case c = 1 is fixed-parameter tractable with respect to ℓ and we show that the case c = 2 is solvable in |V|2ℓ + O(1) time. [ABSTRACT FROM AUTHOR]

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 O(√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 (2O(√k log² k)⋅nO(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-time parameterized algorithms for problems on planar graphs, usually with running time bound 2O(√k log² k)nO(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 could 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. [ABSTRACT FROM AUTHOR]

For the vast majority of local problems on graphs of small treewidth (where, by local we mean that a solution can be verified by checking separately the neighbourhood of each vertex), standard dynamic programming techniques give ctw|V |O(1) time algorithms, where tw is the treewidth of the input graph G = (V, E) and c is a constant. On the other hand, for problems with a global requirement (usually connectivity) the best-known algorithms were naive dynamic programming schemes running in at least twtw time. We bridge this gap by introducing a technique we named Cut&Count that allows to produce ctw|V |O(1) time Monte-Carlo algorithms for most connectivity-type problems, including Hamiltonian Path, Steiner Tree, Feedback Vertex Set and Connected Dominating Set. These results have numerous consequences in various fields, like parameterized complexity, exact and approximate algorithms on planar and H-minorfree graphs and exact algorithms on graphs of bounded degree. The constant c in our algorithms is in all cases small, and in several cases we are able to show that improving those constants would cause the Strong Exponential Time Hypothesis to fail. In all these fields we are able to improve the best-known results for some problems. Also, looking from a more theoretical perspective, our results are surprising since the equivalence relation that partitions all partial solutions with respect to extendability to global solutions seems to consist of at least twtw equivalence classes for all these problems. Our results answer an open problem raised by Lokshtanov, Marx and Saurabh [SODA'11]. In contrast to the problems aimed at minimizing the number of connected components that we solve using Cut&Count as mentioned above, we show that, assuming the Exponential Time Hypothesis, the aforementioned gap cannot be bridged for some problems that aim to maximize the number of connected components like Cycle Packing. [ABSTRACT FROM AUTHOR]

There are numerous examples of the so-called "square root phenomenon" in the field of parameterized algorithms: many of the most fundamental graph problems, parameterized by some natural parameter k, become significantly simpler when restricted to planar graphs and in particular the best possible running time is exponential in O(√ k) instead of O(k) (modulo standard complexity assumptions). We consider a classic optimization problem Subset Traveling Salesman, where we are asked to visit all the terminals T by a minimum-weight closed walk. We investigate the parameterized complexity of this problem in planar graphs, where the number k = |T| of terminals is regarded as the parameter. We show that Subset TSP can be solved in time 2O(√k log k) · nO(1) even on edge-weighted directed planar graphs. This improves upon the algorithm of Klein and Marx [SODA 2014, SIAM, Philadelphia, 2014, pp. 1812-1830] with the same running time that worked only on undirected planar graphs with polynomially large integer weights. [ABSTRACT FROM AUTHOR]

A bramble in an undirected graph G is a family of connected subgraphs of G such that for every two subgraphs H1 and H2 in the bramble either V (H1) \ V (H2) 6=; or there is an edge of G with one endpoint in V (H1) and the second endpoint in V (H2). 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 (n1=2+δ) requires size exponential in (n2δ) for any fixed δ 2 (0; 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 e(k1=2) and size e O(k3=2). (e and e O hide polylogarithmic divisors and factors, 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 e(k1=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 δ 2 (0; 1 2 ], every graph G of treewidth at least k contains a bramble of order e(k1=2+δ) and size 2 eO (k2δ). [ABSTRACT FROM AUTHOR]

In the classic Maximum Weight Independent Set problem, we are given a graph G with a nonnegative weight function on its 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 P6-free graph, that is, a graph that has no path on 6 vertices as an induced subgraph. This improves the polynomial-time algorithm on P5-free graphs of Lokshtanov et al. [15] and the quasipolynomial-time algorithm on P6-free graphs of Lokshtanov et al. [14]. The main technical contribution leading to our main result is enumeration of a polynomial-size family F of vertex subsets with the following property: For every maximal independent set I in the graph, F contains all maximal cliques of some minimal chordal completion of G that does not add any edge incident to a vertex of I. [ABSTRACT FROM AUTHOR]

We show that Odd Cycle Transversal and Vertex Multiway Cut admit deterministic polynomial kernels when restricted to planar graphs and parameterized by the solution size. This answers a question of Saurabh. On the way to these results, we provide an efficient sparsification routine in the flavor of the sparsification routine used for the Steiner Tree problem in planar graphs [Pilipczuk et al., ACM Trans. Algorithms, 14 (2018), 53]. It differs from the previous work because it preserves the existence of low-cost subgraphs that are not necessarily Steiner trees in the original plane graph, but structures that turn into (supergraphs of) Steiner trees after adding all edges between pairs of vertices that lie on a common face. We also show connections between Vertex Multiway Cut and the Vertex Planarization problem, where the existence of a polynomial kernel remains an important open problem. [ABSTRACT FROM AUTHOR]

A theta is a graph made of three internally vertex‐disjoint chordless paths P1=a...b,P2=a...b, P3=a...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 pyramid is a graph made of three chordless paths P1=a...b1,P2=a...b2, P3=a...b3 of length at least 1, two of which have length at least 2, vertex‐disjoint except at a, and such that b1b2b3 is a triangle and no edges exist between the paths except those of the triangles and the three edges incident to a. An even hole is a chordless cycle of even length. For three nonnegative integers i≤j≤k, let Si,j,k be the tree with a vertex v, from which start three paths with i,j, and k edges, respectively. We denote by Kt the complete graph on t vertices. We prove that for all nonnegative integers i,j,k, the class of graphs that contain no theta, no K3, and no Si,j,k as induced subgraphs have bounded treewidth. We prove that for all nonnegative integers i,j,k,t, the class of graphs that contain no even hole, no pyramid, no Kt, and no Si,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. [ABSTRACT FROM AUTHOR]