We prove that a number of computational problems that ask for the largest sparse induced subgraph satisfying some property definable in \(\mathsf{CMSO}_{2}\) 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šová, 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ążewski, 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 study a generalization of the classic Global Min-Cut problem, called Global Label Min-Cut (or sometimes Global Hedge Min-Cut ): the edges of the input (multi)graph are labeled (or partitioned into color classes or hedges), and removing all edges of the same label (color or from the same hedge) costs one. The problem asks to disconnect the graph at minimum cost. While the \(st\) -cut version of the problem is known to be \(\mathsf{NP}\) -hard, the above global cut version is known to admit a quasi-polynomial randomized \(n^{\mathcal{O}(\log\mathrm{OPT})}\) -time algorithm due to Ghaffari, Karger, and Panigrahi [SODA 2017]. They consider this as “strong evidence that this problem is in P ” . We show that this is actually not the case. We complete the study of the complexity of the Global Label Min-Cut problem by showing that the quasi-polynomial running time is probably optimal: We show that the existence of an algorithm with running time \((np)^{o(\log n/(\log\log n)^{2})}\) would contradict the Exponential Time Hypothesis, where \(n\) is the number of vertices, and \(p\) is the number of labels in the input. The key step for the lower bound is a proof that Global Label Min-Cut is \(\mathsf{W}\) [1]-hard when parameterized by the number of uncut labels . In other words, the problem is difficult in the regime where almost all labels need to be cut to disconnect the graph.

We show that for any fixed integer k ⩾ 0, there exists an algorithm that computes the diameter and the eccentricies of all vertices of an input unweighted, undirected n-vertex graph of Euler genus at most k in time 𝒪_k(n^{2-1/25}). Furthermore, for the more general class of graphs that can be constructed by clique-sums from graphs that are of Euler genus at most k after deletion of at most k vertices, we show an algorithm for the same task that achieves the running time bound 𝒪_k(n^{2-1/356} log^{6k} n). Up to today, the only known subquadratic algorithms for computing the diameter in those graph classes are that of [Ducoffe, Habib, Viennot; SICOMP 2022], [Le, Wulff-Nilsen; SODA 2024], and [Duraj, Konieczny, Potępa; ESA 2024]. These algorithms work in the more general setting of K_h-minor-free graphs, but the running time bound is 𝒪_h(n^{2-c_h}) for some constant c_h > 0 depending on h. That is, our savings in the exponent of the polynomial function of n, as compared to the naive quadratic algorithm, are independent of the parameter k. The main technical ingredient of our work is an improved bound on the number of distance profiles, as defined in [Le, Wulff-Nilsen; SODA 2024], in graphs of bounded Euler genus.

Many natural computational problems, including e.g. Max Weight Independent Set, Feedback Vertex Set, or Vertex Planarization, can be unified under an umbrella of finding the largest sparse induced subgraph that satisfies some property definable in CMSO₂ logic. It is believed that each problem expressible with this formalism can be solved in polynomial time in graphs that exclude a fixed path as an induced subgraph. This belief is supported by the existence of a quasipolynomial-time algorithm by Gartland, Lokshtanov, Pilipczuk, Pilipczuk, and Rzążewski [STOC 2021], and a recent polynomial-time algorithm for P₆-free graphs by Chudnovsky, McCarty, Pilipczuk, Pilipczuk, and Rzążewski [SODA 2024]. In this work we extend polynomial-time tractability of all such problems to P₇-free graphs of bounded clique number.

For a fixed integer t ⩾ 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árfá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 𝒪(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. In this work, we refine the argument of Majewski et al. to its arguably final form: we show that a constant number of neighborhoods suffice. The statement of Majewski et al. is one of the two pillars of a recent quasi-polynomial time algorithm for Maximum Weight Independent Set in S_{t,t,t}-free graphs [Gartland et al., STOC 2024]; our work immediately improves the quasi-polynomial function in the running time bound. Furthermore, our result significantly simplifies known polynomial-time algorithms for Maximum Weight Independent Set in S_{t,t,t}-free graphs with an additional sparsity assumption such as bounded degree or excluding a fixed biclique as a subgraph.

A recent work of Abbasi et al. [FOCS 2023] introduced the notion of ε-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 ε-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 ε-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.

Cohen-Addad, Le, Pilipczuk, and Pilipczuk [CLPP23] recently constructed a stochastic embedding with expected 1 + ε distortion of n-vertex planar graphs (with polynomial aspect ratio) into graphs of treewidth O (ε-1 log13n ). Their embedding is the first to achieve polylogarithmic treewidth. However, there remains a large gap between the treewidth of their embedding and the treewidth lower bound of Ω(log n ) shown by Carroll and Goel [CG04]. In this work, we substantially narrow the gap by constructing a stochastic embedding with treewidth O (ε-1 log3 n ).

A decision tree recursively splits a feature space R d and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work considers heuristic algorithms that compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number d of dimensions of the feature space R d , which contains n training examples. We show that it can be solved in O ( n 2 d + 1 ) time, but under reasonable complexity-theoretic assumptions it is not possible to achieve f ( d ) ⋅ n o ( d / log ⁡ d ) running time. The problem is solvable in ( d R ) O ( d R ) ⋅ n 1 + o ( 1 ) time if there are exactly two classes and R is an upper bound on the number of tree leaves labeled with the first class.

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 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: Chain SAT , defined by Chitnis, Egri, and Marx [ESA’13, Algorithmica’17], 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.

Abstract. We study the parameterized problem of satisfying “almost all” constraints of a given formula [Formula: see text] over a fixed, finite Boolean constraint language [Formula: see text], with or without weights. More precisely, for each finite Boolean constraint language [Formula: see text], we consider the following two problems. In Min SAT([Formula: see text]), the input is a formula [Formula: see text] over [Formula: see text] and an integer [Formula: see text], and the task is to find an assignment [Formula: see text] that satisfies all but at most [Formula: see text] constraints of [Formula: see text], or determine that no such assignment exists. In Weighted Min SAT([Formula: see text]), the input additionally contains a weight function [Formula: see text] and an integer [Formula: see text], and the task is to find an assignment [Formula: see text] such that (1) [Formula: see text] satisfies all but at most [Formula: see text] constraints of [Formula: see text], and (2) the total weight of the violated constraints is at most [Formula: see text]. We give a complete dichotomy for the fixed-parameter tractability of these problems: We show that for every Boolean constraint language [Formula: see text], either Weighted Min SAT([Formula: see text]) is [Formula: see text]; or Weighted Min SAT([Formula: see text]) is [Formula: see text]-hard but Min SAT([Formula: see text]) is [Formula: see text]; or Min SAT([Formula: see text]) is [Formula: see text]-hard. This generalizes recent work of Kim et al. [in SODA 2021, SIAM, Philadelphia, 2021, pp. 149–168], which did not consider weighted problems and only considered languages [Formula: see text] that cannot express implications [Formula: see text] (as is used to, e.g., model digraph cut problems). Our result generalizes and subsumes multiple previous results, including the FPT algorithms for Weighted Almost 2-SAT, weighted and unweighted [Formula: see text]-Chain SAT, and Coupled Min-Cut, as well as weighted and directed versions of the latter. The main tool used in our algorithms is the recently developed method of directed flow-augmentation [E. J. Kim et al., in STOC 2022, ACM, 2022, pp. 938–947].

The input in the Minimum-Cost Constraint Satisfaction Problem (MinCSP) over the Point Algebra contains a set of variables, a collection of constraints of the form x < y, x = y, x ≤ y and x ≠ y, and a budget k. The goal is to check whether it is possible to assign rational values to the variables while breaking constraints of total cost at most k. This problem generalizes several prominent graph separation and transversal problems: - MinCSP({<}) is equivalent to Directed Feedback Arc Set, - MinCSP({< , ≤}) is equivalent to Directed Subset Feedback Arc Set, - MinCSP({= ,≠}) is equivalent to Edge Multicut, and - MinCSP({≤ ,≠}) is equivalent to Directed Symmetric Multicut. Apart from trivial cases, MinCSP({Γ}) for Γ ⊆ {< , = , ≤ ,≠} is NP-hard even to approximate within any constant factor under the Unique Games Conjecture. Hence, we study parameterized complexity of this problem under a natural parameterization by the solution cost k. We obtain a complete classification: if Γ ⊆ {< , = , ≤ ,≠} contains both ≤ and ≠, then MinCSP({Γ}) is W[1]-hard, otherwise it is fixed-parameter tractable. For the positive cases, we solve MinCSP({< , = ,≠}), generalizing the FPT results for Directed Feedback Arc Set and Edge Multicut as well as their weighted versions. Our algorithm works by reducing the problem into a Boolean MinCSP, which is in turn solved by flow augmentation. For the lower bounds, we prove that Directed Symmetric Multicut is W[1]-hard, solving an open problem.

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 P6-free graphs. This generalizes the work of Grzesik, Klimošová, Pilipczuk, and Pilipczuk on the Maximum Weight Independent Set problem in P6-free graphs [SODA 2019, TALG 2022], and of Abrishami, Chudnovsky, Pilipczuk, Rzążewski, and Seymour on problems in P5-free graphs [SODA 2021].

Correlation Clustering is a classic clustering objective arising in numerous machine learning and data mining applications. Given a graph G=(V,E), the goal is to partition the vertex set into clusters so as to minimize the number of edges between clusters plus the number of edges missing within clusters. The problem is APX-hard and the best known polynomial time approximation factor is 1.73 by Cohen-Addad, Lee, Li, and Newman [FOCS’23]. They use an LP with |V|1/єΘ(1) variables for some small є. However, due to the practical relevance of correlation clustering, there has also been great interest in getting more efficient sequential and parallel algorithms. The classic combinatorial pivot algorithm of Ailon, Charikar and Newman [JACM’08] provides a 3-approximation in linear time. Like most other algorithms discussed here, this uses randomization. Recently, Behnezhad, Charikar, Ma and Tan [FOCS’22] presented a 3+є-approximate solution for solving problem in a constant number of rounds in the Massively Parallel Computation (MPC) setting. Very recently, Cao, Huang, Su [SODA’24] provided a 2.4-approximation in a polylogarithmic number of rounds in the MPC model and in Õ (|E|1.5) time in the classic sequential setting. They asked whether it is possible to get a better than 3-approximation in near-linear time? We resolve this problem with an efficient combinatorial algorithm providing a drastically better approximation factor. It achieves a ∼ 2−2/13 < 1.847-approximation in sub-linear (Õ(|V|)) sequential time or in sub-linear (Õ(|V|)) space in the streaming setting, and it uses only a constant number of rounds in the MPC model.

We show that the Maximum Weight Independent Set problem (MWIS) can be solved in quasi-polynomial time on H-free graphs (graphs excluding a fixed graph H as an induced subgraph) for every H whose every connected component is a path or a subdivided claw (i.e., a tree with at most three leaves). This completes the dichotomy of the complexity of MWIS in F-free graphs for any finite set F of graphs into NP-hard cases and cases solvable in quasi-polynomial time, and corroborates the conjecture that the cases not known to be NP-hard are actually polynomial-time solvable. The key graph-theoretic ingredient in our result is as follows. Fix an integer t ≥ 1. Let St,t,t be the graph created from three paths on t edges by identifying one endpoint of each path into a single vertex. We show that, given a graph G, one can in polynomial time find either an induced St,t,t in G, or a balanced separator consisting of O(log|V(G)|) vertex neighborhoods in G, or an extended strip decomposition of G (a decomposition almost as useful for recursion for MWIS as a partition into connected components) with each particle of weight multiplicatively smaller than the weight of G. This is a strengthening of a result of Majewski, Masařík, Novotná, Okrasa, Pilipczuk, Rzążewski, and Sokołowski [Transactions on Computation Theory ‍2024] which provided such an extended strip decomposition only after the deletion of O(log|V(G)|) vertex neighborhoods. To reach the final result, we employ an involved branching strategy that relies on the structural lemma presented above.

Abstract. 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 [Formula: see text], we denote a path on [Formula: see text] 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 [Formula: see text]-free graphs. Each of the above results resolves a corresponding long-standing open problem. An extended [Formula: see text] is a five-vertex hole with an additional vertex adjacent to one or two consecutive vertices of the hole. Let [Formula: see text] be the class of graphs excluding an extended [Formula: see text] and holes of length at least 6 as induced subgraphs; [Formula: see text] contains all long-hole–free graphs and all [Formula: see text]-free graphs. We show that, given an [Formula: see text]-vertex graph [Formula: see text] with vertex weights and an integer [Formula: see text], one can, in time, [Formula: see text] find a maximum-weight induced subgraph of [Formula: see text] of treewidth less than [Formula: see text]. 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 [Formula: see text] for fixed [Formula: see text], 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 [Formula: see text]-free [Lokshtanov, Vatshelle, and Villanger, SODA 2014, pp. 570–581] or [Formula: see text]-free graphs [Grzesik, Klimošová, 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. 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 [Formula: see text] for any [Formula: see text]. 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 [Formula: see text]-free graphs, that is, graphs not containing a fixed graph [Formula: see text] as an induced subgraph, the problem is known to remain NP-hard and APX-hard whenever [Formula: see text] 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 [Formula: see text] 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 [Formula: see text] such as [Formula: see text], [Formula: see text], the claw, or the fork. We prove that for every such “possibly tractable” graph [Formula: see text] there exists an algorithm that, given an [Formula: see text]-free graph [Formula: see text] and an accuracy parameter [Formula: see text], finds an independent set in [Formula: see text] of cardinality within a factor of [Formula: see text] of the optimum in time exponential in a polynomial of [Formula: see text] and [Formula: see text]. Furthermore, an independent set of maximum size can be found in subexponential time [Formula: see text]. That is, we show that for every graph [Formula: see text] for which Maximum Independent Set is not known to be APX-hard and SUBEXP-hard in [Formula: see text]-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. We confirm a conjecture of Gartland and Lokshtanov [SODA 2023]: if for a hereditary graph class [Formula: see text] there exists a constant [Formula: see text] such that no member of [Formula: see text] contains a [Formula: see text]-creature as an induced subgraph or a [Formula: see text]-skinny-ladder as an induced minor, then there exists a polynomial [Formula: see text] such that every [Formula: see text] contains at most [Formula: see text] 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 [Formula: see text]. 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. 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: In weighted undirected graphs, Multicut is fixed-parameter tractable (FPT) in both the edge- and the vertex-deletion version. The weighted version of Group Feedback Vertex Set is FPT, even with oracle access to group operations. 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.

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 -𝒪( k 4 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.

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 P 3 s (no pair of P 3 s 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 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 ℋ. 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.

A decision tree recursively splits a feature space \mathbb{R}^d and then assigns class labels based on the resulting partition. Decision trees have been part of the basic machine-learning toolkit for decades. A large body of work considers heuristic algorithms that compute a decision tree from training data, usually aiming to minimize in particular the size of the resulting tree. In contrast, little is known about the complexity of the underlying computational problem of computing a minimum-size tree for the given training data. We study this problem with respect to the number d of dimensions of the feature space \mathbb{R}^d, which contains n training examples. We show that it can be solved in O(n^(2d + 1)) time, but under reasonable complexity-theoretic assumptions it is not possible to achieve f(d) * n^o(d / log d) running time. The problem is solvable in (dR)^O(dR) * n^(1+o(1)) time, if there are exactly two classes and R is an upper bound on the number of tree leaves labeled with the first class.

We prove that there is a randomized polynomialtime algorithm that given an edge-weighted graph G excluding a fixed-minor Q on n vertices and an accuracy parameter $\varepsilon\gt$ 0, constructs an edge-weighted graph H and an embedding $\eta: V(G) \rightarrow 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 $\operatorname{dist}_{H}(\eta(u), \eta(v)) \geqslant \operatorname{dist}_{G}(u, v)$ always and $\mathbb{E}\left[\operatorname{dist}_{H}(\eta(u), \eta(v))\right] \leqslant(1+\varepsilon) \operatorname{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.

Constraint satisfaction problems form a nicely behaved class of problems that lends itself to complexity classification results. From the point of view of parameterized complexity, a natural task is to classify the parameterized complexity of MinCSP problems parameterized by the number of unsatisfied constraints. In other words, we ask whether we can delete at most $k$ constraints, where $k$ is the parameter, to get a satisfiable instance. In this work, we take a step towards classifying the parameterized complexity for an important infinite-domain CSP: Allen's interval algebra (IA). This CSP has closed intervals with rational endpoints as domain values and employs a set $A$ of 13 basic comparison relations such as ``precedes'' or ``during'' for relating intervals. IA is a highly influential and well-studied formalism within AI and qualitative reasoning that has numerous applications in, for instance, planning, natural language processing and molecular biology. We provide an FPT vs. W[1]-hard dichotomy for MinCSP$(Γ)$ for all $Γ\subseteq A$. IA is sometimes extended with unions of the relations in $A$ or first-order definable relations over $A$, but extending our results to these cases would require first solving the parameterized complexity of Directed Symmetric Multicut, which is a notorious open problem. Already in this limited setting, we uncover connections to new variants of graph cut and separation problems. This includes hardness proofs for simultaneous cuts or feedback arc set problems in directed graphs, as well as new tractable cases with algorithms based on the recently introduced flow augmentation technique. Given the intractability of MinCSP$(A)$ in general, we then consider (parameterized) approximation algorithms and present a factor-$2$ fpt-approximation algorithm.

We study the parameterized problem of satisfying “almost all” constraints of a given formula F over a fixed, finite Boolean constraint language Γ, with or without weights. More precisely, for each finite Boolean constraint language Γ, we consider the following two problems. In MIN SAT(T), the input is a formula F over Γ and an integer k, and the task is to find an assignment α : V(F) → {0,1} that satisfies all but at most k constraints of F, or determine that no such assignment exists. In WEIGHTED MIN SAT(Γ), the input additionally contains a weight function ω : F → ℤ+ and an integer W, and the task is to find an assignment α such that (1) α satisfies all but at most k constraints of F, and (2) the total weight of the violated constraints is at most W. We give a complete dichotomy for the fixed-parameter tractability of these problems: We show that for every Boolean constraint language Γ, either WEIGHTED MIN SAT(Γ) is FPT; or WEIGHTED MIN SAT(Γ) is W[1]-hard but MIN SAT(Γ) is FPT; or MIN SAT (Γ) is W[1]-hard. This generalizes recent work of Kim et al. (SODA 2021) which did not consider weighted problems, and only considered languages Γ that cannot express implications (u → v) (as is used to, e.g., model digraph cut problems). Our result generalizes and subsumes multiple previous results, including the FPT algorithms for WEIGHTED Almost 2-SAT, weighted and unweighted ℓ-CHAIN SAT, and COUPLED MIN-CUT, as well as weighted and directed versions of the latter. The main tool used in our algorithms is the recently developed method of directed flow-augmentation (Kim et al., STOC 2022). * This research is a part of a project that have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme Grant Agreement 714704 (M. Pilipczuk). Eun Jung Kim is supported by the grant from French National Research Agency under JCJC program (ASSK: ANR-18-CE40-0025-01). The full version of the paper can be accessed at https://arxiv.org/abs/2207.07422.

We show fixed-parameter tractability of the DIRECTED MULTICUT problem with three terminal pairs (with a randomized algorithm). In this problem we are given a directed graph G, three pairs of vertices (called terminals) (s1, t1), (s2, t2), (s3, t3), and an integer k and we want to find a set of at most k non-terminal vertices in G that intersect all s1t1-paths, all s2t2-paths, and all s3t3-paths. The parameterized complexity of this problem has been open since Chitnis, Hajiaghayi, and Marx proved fixed-parameter tractability of the two-terminal-pairs case at SODA 2012, and Pilipczuk and Wahlström proved the W[1]-hardness of the four-terminal-pairs case at SODA 2016. On the technical side, we use two recent developments in parameterized algorithms. Using the technique of directed flow-augmentation [Kim, Kratsch, Pilipczuk, Wahlström, STOC 2022] we cast the problem as a CSP problem with few variables and constraints over a large ordered domain. We observe that this problem can be in turn encoded as an FO model-checking task over a structure consisting of a few 0-1 matrices. We look at this problem through the lenses of twin-width, a recently introduced structural parameter [Bonnet, Kim, Thomassé, Watrigant, FOCS 2020]: By a recent characterization [Bonnet, Giocanti, Ossona de Mendez, Simon, Thomassé, Toruńczyk, STOC 2022] the said FO model-checking task can be done in FPT time if the said matrices have bounded grid rank. To complete the proof, we show an irrelevant vertex rule: If any of the matrices in the said encoding has a large grid minor, a vertex corresponding to the “middle” box in the grid minor can be proclaimed irrelevant — not contained in the sought solution — and thus reduced. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.07425. The research leading to the results presented in this paper was partially carried out during the Parameterized Algorithms Retreat of the University of Warsaw, PARUW 2022, held in Bedlewo in April 2022. This research is a part of projects that have received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme Grant Agreement 714704 (TM, MP) and 648527 (MH), from the Alexander von Humboldt Foundation (MS), from the Research Council of Norway (LJ), and by the Federal Ministry of Education and Research (BMBF) and by a fellowship within the IFI programme of the German Academic Exchange Service (DAAD). (MH).

We study a generalization of the classic GLOBAL MIN-CUT problem, called GLOBAL LABEL MIN-CUT (or sometimes GLOBAL HEDGE MIN-CUT): the edges of the input (multi)graph are labeled (or partitioned into color classes or hedges), and removing all edges of the same label (color or from the same hedge) costs one. The problem asks to disconnect the graph at minimum cost. While the st-cut version of the problem is known to be NP-hard, the above global cut version is known to admit a quasi-polynomial randomized nO(log OPT)-time algorithm due to Ghaffari, Karger, and Panigrahi [SODA 2017]. They consider this as “strong evidence that this problem is in P”. We show that this is actually not the case. We complete the study of the complexity of the Global Label Min-Cut problem by showing that the quasi-polynomial running time is probably optimal: We show that the existence of an algorithm with running time (np)o(log n/(log log n)2) would contradict the Randomized Exponential Time Hypothesis, where n is the number of vertices, and p is the number of labels in the input. The key step for the lower bound is a proof that Global Label Min-Cut is W[1]-hard when parameterized by the number of uncut labels. In other words, the problem is difficult in the regime where almost all labels need to be cut to disconnect the graph. To turn this lower bound into a quasi-polynomial-time lower bound, we also needed to revisit the framework due to Marx [Theory Comput. 2010] of proving lower bounds assuming Exponential Time Hypothesis through the SUBGRAPH ISOMORPHISM problem parameterized by the number of edges of the pattern. Here, we provide an alternative simplified proof of the hardness of this problem that is more versatile with respect to the choice of the regimes of the parameters. * This research is a part of a project that has received funding from the European Research Council (ERC) under the European Union's Horizon 2020 research and innovation programme Grant Agreement 714704 (LJ, TM, MP, US) and from the Research Council of Norway (LJ).

Abstract The notion offorbidden-transition graphsallows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex ispermittedorforbidden; a walk iscompatibleif all pairs of consecutive edges on the walk are permitted. Forbidden-transition graphs and related models have found applications in a variety of fields, such as routing in optical telecommunication networks, road networks, and bio-informatics. A widely-studied special case are edge-colored graphs, where a compatible walk is forbidden to take two edges of the same color in a row. We initiate the study of fundamental problems on finding paths, cycles and walks in forbidden-transition graphs from the point of view of parameterized complexity, including an in-depth study of tractability with regards to various graph-width parameters. Among several results, we prove that finding a simple compatible path between given endpoints in a forbidden-transition graph isW[1]-hard when parameterized by the vertex-deletion distance to a linear forest (so it is also hard when parameterized by pathwidth or treewidth). On the other hand, we show an algebraic trick that yields tractability when parameterized by treewidth for finding a compatible Hamiltonian cycle in the edge-colored graph setting.

We confirm a conjecture of Gartland and Lokshtanov [arXiv:2007.08761]: if for a hereditary graph class 𝒢 there exists a constant k such that no member of 𝒢 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 ∈ 𝒢 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 𝒢. 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é, 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árfás' 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.

In this paper, we introduce a new class of parameterized problems, which we call XALP: the class of all parameterized problems that can be solved in $f(k)n^{O(1)}$ time and $f(k)\log n$ space on a non-deterministic Turing Machine with access to an auxiliary stack (with only top element lookup allowed). Various natural problems on `tree-structured graphs' are complete for this class: we show that List Colouring and All-or-Nothing Flow parameterized by treewidth are XALP-complete. Moreover, Independent Set and Dominating Set parameterized by treewidth divided by $\log n$, and Max Cut parameterized by cliquewidth are also XALP-complete. Besides finding a `natural home' for these problems, we also pave the road for future reductions. We give a number of equivalent characterisations of the class XALP, e.g., XALP is the class of problems solvable by an Alternating Turing Machine whose runs have tree size at most $f(k)n^{O(1)}$ and use $f(k)\log n$ space. Moreover, we introduce `tree-shaped' variants of Weighted CNF-Satisfiability and Multicolour Clique that are XALP-complete.

We show a flow-augmentation algorithm in directed graphs: There exists a randomized polynomial-time algorithm that, given a directed graph G, two integers 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 minimum st-cut in the resulting graph.

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)· nO(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, which reveals that every such graph can be canonically decomposed into a part that admits few automorphisms and a part that has bounded treewidth.

Abstract. We prove the following theorem. Given a planar graph [Formula: see text] and an integer [Formula: see text], it is possible in polynomial time to randomly sample a subset [Formula: see text] of vertices of [Formula: see text] with the following properties: [Formula: see text] induces a subgraph of [Formula: see text] of treewidth [Formula: see text], and for every connected subgraph [Formula: see text] of [Formula: see text] on at most [Formula: see text] vertices, the probability that [Formula: see text] covers the whole vertex set of [Formula: see text] is at least [Formula: see text], where [Formula: see text] is the number of vertices of [Formula: see text]. 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 [Formula: see text]. 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 [Formula: see text]-Path, Weighted [Formula: see text]-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.

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 $\mathcal{O}(\sqrt{k})$ instead of $\mathcal{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 $2^{\mathcal{O}(\sqrt{k}\log k)}\cdot n^{\mathcal{O}(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.

The Directed Grid Theorem, stating that there is a function $f$ such that a directed graph 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, was proved 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$.

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 c tw | 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 tw tw time. We bridge this gap by introducing a technique we named Cut&Count that allows to produce c tw | 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 -minor-free 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 tw tw 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 .

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 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. [ 15 ] and the quasipolynomial-time algorithm on P 6 -free graphs of Lokshtanov et al. [ 14 ]. The main technical contribution leading to our main result is enumeration of a polynomial-size family ℱ of vertex subsets with the following property: For every maximal independent set I in the graph, ℱ contains all maximal cliques of some minimal chordal completion of G that does not add any edge incident to a vertex of I .

At IPEC 2020, Bergougnoux, Bonnet, Brettell, and Kwon (Close Relatives of Feedback Vertex Set Without Single-Exponential Algorithms Parameterized by Treewidth, IPEC 2020, LIPIcs vol. 180, pp. 3:1-3:17) showed that a number of problems related to the classic Feedback Vertex Set (FVS) problem do not admit a 2^{o(k log k)} ⋅ n^{𝒪(1)}-time algorithm on graphs of treewidth at most k, assuming the Exponential Time Hypothesis. This contrasts with the 3^{k} ⋅ k^{𝒪(1)} ⋅ 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^{𝒪(k log k)} ⋅ 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^{𝒪(k log k)} ⋅ n, if the input graph is given as a cliquewidth expression of size n and width k. - Odd Cycle Transversal can be solved in time 4^k ⋅ k^{𝒪(1)} ⋅ n if the input graph is given as a cliquewidth expression of size n and width k. Furthermore, the existence of a constant ε > 0 and an algorithm performing this task in time (4-ε)^k ⋅ n^{𝒪(1)} would contradict the Strong Exponential Time Hypothesis. A common theme of the first two algorithmic results is to represent connectivity properties of the current graph in a state of a dynamic programming algorithm as an auxiliary forest with 𝒪(k) nodes. This results in a 2^{𝒪(k log k)} bound on the number of states for one node of the tree decomposition or cliquewidth expression and allows to compare two states in k^{𝒪(1)} time, resulting in linear time dependency on the size of the graph or the input cliquewidth expression.

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.

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 be the class of graphs excluding an extended C5 and holes of length at least 6 as induced subgraphs; contains all long-hole-free graphs and all P5-free graphs. We show that, given an n-vertex graph G ∊ with vertex weights and an integer k, one can in time 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. 2001] and extended by Fomin, Todinca, and Villanger [SIAM J. Comput. 2015], this framework allows to solve high 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 [SODA 2014] or P6-free graphs [SODA 2019]), 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 potential maximal clique: a superset of the maximal clique that intersects the sought solution only in the vertices of the potential maximal clique. This strengthening of the framework not only allows us to obtain our main result, but also leads to significant simplifications of reasonings in previous papers.

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 , 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řák 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 dO(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 . In the second case, the amortized update time is . In both cases we assume access to a dictionary on the edges of G.

We present a new technique for designing fixed-parameter algorithms for graph cut problems in undirected graphs, which we call flow augmentation. Our technique is applicable to problems that can be phrased as a search for an (edge) (s, t)-cut of cardinality at most k in an undirected graph G with designated terminals s and t. More precisely, we consider problems where an (unknown) solution is a set Z ⊆ E(G) of size at most k such that •in G – Z, s and t are in distinct connected components,•every edge of Z connects two distinct connected components of G – Z, and•if we define the set Zs, t ⊆ Z as those edges e ∊ Z for which there exists an (s, t)-path Pe with E(Pe) ∩ Z = {e}, then Zs, t separates s from t. We prove that in the above scenario one can in randomized time k(1) (|V(G)| + |E(G)|) add a number of edges to the graph so that with probably at least 2–(k log k) no added edge connects two components of G – Z, and Zs, t becomes a minimum cut between s and t. This additional property becomes a handy lever in applications. For example, consider the question of an (s, t)-cut of cardinality at most k and of minimum possible weight (assuming edge weights in G). While the problem is NP-hard in general, it easily reduces to the maximum flow / minimum cut problem if we additionally assume that k is the minimum possible cardinality of an (s, t)-cut in G. Hence, we immediately obtain that the aforementioned problem admits an 2(k log k) n(1)-time randomized fixed-parameter algorithm. We apply our method to obtain a randomized fixed-parameter algorithm for a notorious “hard nut” graph cut problem we call Coupled Min-Cut. This problem emerges out of the study of FPT algorithms for Min CSP problems (see below), and was unamenable to other techniques for parameterized algorithms in graph cut problems, such as Randomized Contractions, Treewidth Reduction or Shadow Removal. In fact, we go one step further. To demonstrate the power of the approach, we consider more generally the Boolean Min CSP(Γ)-problems, a.k.a. Min SAT(Γ), parameterized by the solution cost. This is a framework of optimization problems that includes problems such as Almost 2-SAT and the notorious i-Chain SAT problem. We are able to show that every problem Min SAT(Γ) is either (1) FPT, (2) W[1]-hard, or (3) able to express the soft constraint (u → v), and thereby also the min-cut problem in directed graphs. All the W[1]-hard cases were known or immediate, and the main new result is an FPT algorithm for a generalization of Coupled Min-Cut. In other words, flow-augmentation is powerful enough to let us solve every fixed-parameter tractable problem in the class, except those that explicitly encompass directed graph cuts.

Given two disjoint sets W1 and W2 of points in the plane, the Optimal Discretization problem asks for the minimum size of a family of horizontal and vertical lines that separate W1 from W2, that is, in every region into which the lines partition the plane there are either only points of W1, or only points of W2, 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 W1 × W2 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 , 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.

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 P₃s (no pair of P₃s in H 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 𝓁+|H| 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 H) and when each vertex is in at most 23 P₃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₃s. 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.

For an integer t, a graph G is called C>t-free if G does not contain any induced cycle on more than t vertices. We prove the following statement: for every pair of integers d and t and a statement φ, there exists an algorithm that, given an n-vertex C>t-free graph G with weights on vertices, finds in time n(log3 n) a maximum-weight vertex subset S such that G[S] has degeneracy at most d and satisfies φ. The running time can be improved to n(log2 n) assuming G is Pt-free, that is, G does not contain an induced path on t vertices. This expands the recent results of the authors [FOCS 2020 and SOSA 2021] on the Maximum Weight Independent Set problem on Pt-free graphs in two directions: by encompassing the more general setting of C>t-free graphs, and by being applicable to a much wider variety of problems, such as Maximum Weight Induced Forest or Maximum Weight Induced Planar Graph.

Abstract Low-treedepth colorings are an important tool for algorithms that exploit structure in classes of bounded expansion; they guarantee subgraphs that use few colors have bounded treedepth. These colorings have an implicit tradeoff between the total number of colors used and the treedepth bound, and prior empirical work suggests that the former dominates the run time of existing algorithms in practice. We introduce p-linear colorings as an alternative to the commonly used p-centered colorings. They can be efficiently computed in bounded expansion classes and use at most as many colors as p-centered colorings. Although a set of $$k k < p colors from a p-centered coloring induces a subgraph of treedepth at most k, the same number of colors from a p-linear coloring may induce subgraphs of larger treedepth. We establish a polynomial upper bound on the treedepth in general graphs, and give tighter bounds in trees and interval graphs via constructive coloring algorithms. We also give a co-NP-completeness reduction for recognizing p-linear colorings and discuss ways to overcome this limitation in practice.

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 all 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)$ either is 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 [Proceedings of the 2018 Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 234--246]. 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)$.

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.

We show an algorithm that, given an n -vertex graph G and a parameter k , in time 2 O ( k log k ) n O (1) finds a tree decomposition of G with the following properties: — every adhesion of the tree decomposition is of size at most k , and — every bag of the tree decomposition is ( i , i )-unbreakable in G for every 1 ⩽ i ⩽ k . Here, a set X ⊆ V ( G ) is ( a , b )-unbreakable in G if for every separation ( A , B ) of order at most b in G , we have | A \cap X | ⩽ a or | B ∩ X | ⩽ a . The resulting tree decomposition has arguably best possible adhesion size bounds and unbreakability guarantees. Furthermore, the parametric factor in the running time bound is significantly smaller than in previous similar constructions. These improvements allow us to present parameterized algorithms for M INIMUM B ISECTION , S TEINER C UT , and S TEINER M ULTICUT with improved parameteric factor in the running time bound. The main technical insight is to adapt the notion of lean decompositions of Thomas and the subsequent construction algorithm of Bellenbaum and Diestel to the parameterized setting.

The notion of forbidden-transition graphs allows for a robust generalization of walks in graphs. In a forbidden-transition graph, every pair of edges incident to a common vertex is permitted or forbidden; a walk is compatible if all pairs of consecutive edges on the walk are permitted. Forbidden-transition graphs and related models have found applications in a variety of fields, such as routing in optical telecommunication networks, road networks, and bio-informatics. We initiate the study of fundamental connectivity problems from the point of view of parameterized complexity, including an in-depth study of tractability with regards to various graph-width parameters. Among several results, we prove that finding a simple compatible path between given endpoints in a forbidden-transition graph is W[1]-hard when parameterized by the vertex-deletion distance to a linear forest (so it is also hard when parameterized by pathwidth or treewidth). On the other hand, we show an algebraic trick that yields tractability when parameterized by treewidth of finding a properly colored Hamiltonian cycle in an edge-colored graph; properly colored walks in edge-colored graphs is one of the most studied special cases of compatible walks in forbidden-transition graphs.

Publikacja bezkosztowa

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. That is, we show that for every graph H for which Maximum Independent Set is not known to be APX-hard in H-free graphs, the problem admits a quasi-polynomial time approximation scheme 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.

In this paper, we study multi-budgeted variants of the classic minimum cut problem and graph separation problems that turned out to be important in parameterized complexity: Skew Multicut and Directed Feedback Arc Set. In our generalization, we assign colors $$1,2,\ldots ,\ell $$ to some edges and give separate budgets $$k_{1},k_{2},\ldots ,k_{\ell }$$ for colors $$1,2,\ldots ,\ell $$ . For every color $$i\in \{1,\ldots ,\ell \}$$ , let $$E_{i}$$ be the set of edges of color i. The solution C for the multi-budgeted variant of a graph separation problem not only needs to satisfy the usual separation requirements (i.e., be a cut, a skew multicut, or a directed feedback arc set, respectively), but also needs to satisfy that $$|C\cap E_{i}|\le k_{i}$$ for every $$i\in \{1,\ldots ,\ell \}$$ . Contrary to the classic minimum cut problem, the multi-budgeted variant turns out to be NP-hard even for $$\ell = 2$$ . We propose FPT algorithms parameterized by $$k=k_{1}+\cdots +k_{\ell }$$ for all three problems. To this end, we develop a branching procedure for the multi-budgeted minimum cut problem that measures the progress of the algorithm not by reducing k as usual, by but elevating the capacity of some edges and thus increasing the size of maximum source-to-sink flow. Using the fact that a similar strategy is used to enumerate all important separators of a given size, we merge this process with the flow-guided branching and show an FPT bound on the number of (appropriately defined) important multi-budgeted separators. This allows us to extend our algorithm to the Skew Multicut and Directed Feedback Arc Set problems. Furthermore, we show connections of the multi-budgeted variants with weighted variants of the directed cut problems and the Chain $$\ell $$ -SAT problem, whose parameterized complexity remains an open problem. We show that these problems admit a bounded-in-parameter number of “maximally pushed” solutions (in a similar spirit as important separators are maximally pushed), giving somewhat weak evidence towards their tractability.

Abstract We study the Independent Feedback Vertex Set problem — a variant of the classic Feedback Vertex Set problem where, given a graph G and an integer k, the problem is to decide whether there exists a vertex set $S\subseteq V(G)$ S ⊆ V ( G ) such that G ∖ S is a forest and S is an independent set of size at most k. We present an $\mathcal {O}^{\ast }((1+\varphi ^{2})^{k})$ O ∗ ( ( 1 + φ 2 ) k ) -time FPT algorithm for this problem, where φ < 1.619 is the golden ratio, improving the previous fastest $\mathcal {O}^{\ast }(4.1481^{k})$ O ∗ ( 4.148 1 k ) -time algorithm given by Agrawal et al. (2016). The exponential factor in our time complexity bound matches the fastest deterministic FPT algorithm for the classic Feedback Vertex Set problem. On the technical side, the main novelty is a refined measure of an input instance in a branching process, that allows for a simpler and more concise description and analysis of the algorithm.

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.

No abstract available.

We consider the k-Median problem on planar graphs: given an edge-weighted planar graph G, a set of clients C subseteq V(G), a set of facilities F subseteq V(G), and an integer parameter k, the task is to find a set of at most k facilities whose opening minimizes the total connection cost of clients, where each client contributes to the cost with the distance to the closest open facility. We give two new approximation schemes for this problem: - FPT Approximation Scheme: for any epsilon>0, in time 2^{O(k epsilon^{-3} log (k epsilon^{-1}))}* n^O(1) we can compute a solution that has connection cost at most (1+epsilon) times the optimum, with high probability. - Efficient Bicriteria Approximation Scheme: for any epsilon>0, in time 2^{O(epsilon^{-5} log (epsilon^{-1}))}* n^O(1) we can compute a set of at most (1+epsilon)k facilities whose opening yields connection cost at most (1+epsilon) times the optimum connection cost for opening at most k facilities, with high probability. As a direct corollary of the second result we obtain an EPTAS for Uniform Facility Location on planar graphs, with same running time. Our main technical tool is a new construction of a "coreset for facilities" for k-Median in planar graphs: we show that in polynomial time one can compute a subset of facilities F_0 subseteq F of size k * (log n/epsilon)^O(epsilon^{-3}) with a guarantee that there is a (1+epsilon)-approximate solution contained in F_0.

The celebrated Erdős-Pósa 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 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). 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.

We consider the classic Facility Location problem on planar graphs (non-uniform, uncapacitated). Given an edge-weighted planar graph G, a set of clients C ⊆ V(G), a set of facilities F ⊆ V(G), and opening costs open: F → R≥0, the goal is to find a subset D of F that minimizes ΣcϵCminfϵDdist(c,f) + ΣfϵDopen(f). The Facility Location problem remains one of the most classic and fundamental optimization problem for which it is not known whether it admits a polynomial-time approximation scheme (PTAS) on planar graphs despite significant effort for obtaining one. We solve this open problem by giving an algorithm that for any ε>0, computes a solution of cost at most (1+ε) times the optimum in time n (2O(ε(-2) log(1/ε))) .

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 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. [11], and the quasipolynomial-time algorithm on P6-free graphs of Lokshtanov et al. [12]. The main technical contribution leading to our main result is enumeration of a polynomial-size family ℱ of vertex subsets with the following property: for every maximal independent set I in the graph, ℱ contains all maximal cliques of some minimal chordal completion of G that does not add any edge incident to a vertex of I.

In algorithmic graph theory, a classic open question is to determine the complexity of the Maximum Independent Set problem on $$P_t$$ -free graphs, that is, on graphs not containing any induced path on t vertices. So far, polynomial-time algorithms are known only for $$t\le 5$$ (Lokshtanov et al., in: Proceedings of the twenty-fifth annual ACM-SIAM symposium on discrete algorithms, SODA 2014, Portland, OR, USA, January 5–7, 2014, pp 570–581, 2014), and an algorithm for $$t=6$$ announced recently (Grzesik et al. in Polynomial-time algorithm for maximum weight independent set on $${P}_6$$ -free graphs. CoRR, arXiv:1707.05491 , 2017). Here we study the existence of subexponential-time algorithms for the problem: we show that for any $$t\ge 1$$ , there is an algorithm for Maximum Independent Set on $$P_t$$ -free graphs whose running time is subexponential in the number of vertices. Even for the weighted version MWIS, the problem is solvable in $$2^{\mathcal {O}(\sqrt{tn \log n})}$$ time on $$P_t$$ -free graphs. For approximation of MIS in broom-free graphs, a similar time bound is proved. Scattered Set is the generalization of Maximum Independent Set where the vertices of the solution are required to be at distance at least d from each other. We give a complete characterization of those graphs H for which d-Scattered Set on H-free graphs can be solved in time subexponential in the size of the input (that is, in the number of vertices plus the number of edges):

The notion of Turing kernelization investigates whether a polynomial-time algorithm can solve an NP-hard problem, when it is aided by an oracle that can be queried for the answers to bounded-size subproblems. One of the main open problems in this direction is whether $$k$$ -Path admits a polynomial Turing kernel: can a polynomial-time algorithm determine whether an undirected graph has a simple path of length k, using an oracle that answers queries of size $$k^{\mathscr {O} (1)}$$ ? We show this can be done when the input graph avoids a fixed graph H as a topological minor, thereby significantly generalizing an earlier result for bounded-degree and $$K_{3,t}$$ -minor-free graphs. Moreover, we show that $$k$$ -Path even admits a polynomial Turing kernel when the input graph is not H-topological-minor-free itself, but contains a known vertex modulator of size bounded polynomially in the parameter, whose deletion makes it so. To obtain our results, we build on the graph minors decomposition to show that any H-topological-minor-free graph that does not contain a k-path, has a separation that can safely be reduced after communication with the oracle.

Given an edge-weighted graph G with a set $$Q$$ of k terminals, a mimicking network is a graph with the same set of terminals that exactly preserves the size of minimum cut between any partition of the terminals. A natural question in the area of graph compression is to provide as small mimicking networks as possible for input graph G being either an arbitrary graph or coming from a specific graph class. We show an exponential lower bound for cut mimicking networks in planar graphs: there are edge-weighted planar graphs with k terminals that require $$2^{k-2}$$ edges in any mimicking network. This nearly matches an upper bound of $$\mathcal {O}(k 2^{2k})$$ of Krauthgamer and Rika (in: Khanna (ed) Proceedings of the twenty-fourth annual ACM-SIAM symposium on discrete algorithms, SODA 2013, New Orleans, 2013) and is in sharp contrast with the upper bounds of $$\mathcal {O}(k^2)$$ and $$\mathcal {O}(k^4)$$ under the assumption that all terminals lie on a single face (Goranci et al., in: Pruhs and Sohler (eds) 25th Annual European symposium on algorithms (ESA 2017), 2017, arXiv:1702.01136 ; Krauthgamer and Rika in Refined vertex sparsifiers of planar graphs, 2017, arXiv:1702.05951 ). As a side result we show a tight example for double-exponential upper bounds given by Hagerup et al. (J Comput Syst Sci 57(3):366–375, 1998), Khan and Raghavendra (Inf Process Lett 114(7):365–371, 2014), and Chambers and Eppstein (J Gr Algorithms Appl 17(3):201–220, 2013).

We show that a problem of deleting a minimum number of vertices from a graph to obtain a graph embeddable on a surface of a given Euler genus is solvable in time $$2^{C_g \cdot k^2 \log k} n^{\mathcal {O}(1)}$$ , where k is the size of the deletion set, $$C_g$$ is a constant depending on the Euler genus g of the target surface, and n is the size of the input graph. On the way to this result, we develop an algorithm solving the problem in question in time $$2^{\mathcal {O}((t+g) \log (t+g))} n$$ given a tree decomposition of the input graph of width t. The results generalize previous algorithms for the surface being a sphere by Marx and Schlotter (Algorithmica 62(3–4):807–822, 2012. https://doi.org/10.1007/s00453-010-9484-z ), Kawarabayashi (in: 50th annual IEEE symposium on foundations of computer science, FOCS 2009, IEEE Computer Society, pp 639–648, 2009. https://doi.org/10.1109/FOCS.2009.45 ) and Jansen et al. (in: Chekuri (ed) 25th annual ACM-SIAM symposium on discrete algorithms, SODA 2014, SIAM, pp 1802–1811, 2014. https://doi.org/10.1137/1.9781611973402.130 ).

In the Edge Bipartization problem one is given an undirected graph G and an integer k, and the question is whether k edges can be deleted from G so that it becomes bipartite. Guo et al. (J Comput Syst Sci 72(8):1386–1396, 2006) proposed an algorithm solving this problem in time $$\mathcal {O}(2^k\cdot {m}^2)$$ ; today, this algorithm is a textbook example of an application of the iterative compression technique. Despite extensive progress in the understanding of the parameterized complexity of graph separation problems in the recent years, no significant improvement upon this result has been yet reported. We present an algorithm for Edge Bipartization that works in time $$\mathcal {O}(1.977^k\cdot {nm})$$ , which is the first algorithm with the running time dependence on the parameter better than $$2^k$$ . To this end, we combine the general iterative compression strategy of Guo et al. (2006), the technique proposed by Wahlström (in: Proceedings of SODA’14, SIAM, 2014) of using a polynomial-time solvable relaxation in the form of a Valued Constraint Satisfaction Problem to guide a bounded-depth branching algorithm, and an involved Measure&Conquer analysis of the recursion tree.

In the classic Minimum Bisection problem we are given as input an undirected graph $G$ and an integer $k$. The task is to determine whether there is a partition of $V(G)$ into two parts $A$ and $B$ such that $||A|-|B|| \leq 1$ and there are at most $k$ edges with one endpoint in $A$ and the other in $B$. In this paper we give an algorithm for Minimum Bisection with running time $2^{\mathcal{O}(k^3)}n^3 \log^3 n$. This is the first fixed parameter tractable algorithm for Minimum Bisection parameterized by $k$. At the core of our algorithm lies a new decomposition theorem that states that every graph $G$ can be decomposed by small separators into parts where each part is “highly connected” in the following sense: any separator of bounded size can separate only a limited number of vertices from each part of the decomposition. Our techniques generalize to the weighted setting, where we seek a bisection of minimum weight among solutions that contain at most $k$ edges.

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(sqrt(k)) instead of O(k) (modulo standard complexity assumptions). We consider two classic optimization problems parameterized by the number of terminals. The Steiner Tree problem asks for a minimum-weight tree connecting a given set of terminals T in an edge-weighted graph. In the Subset Traveling Salesman problem we are asked to visit all the terminals T by a minimum-weight closed walk. We investigate the parameterized complexity of these problems in planar graphs, where the number k = |T| of terminals is regarded as the parameter. Our results are the following: • Subset TSP can be solved in time 2^O(sqrt(k) log k) . n^O(1) even on edge-weighted directed planar graphs. This improves upon the algorithm of Klein and Marx [SODA 2014] with the same running time that worked only on undirected planar graphs with polynomially large integer weights. • Assuming the Exponential-Time Hypothesis, Steiner Tree on undirected planar graphs cannot be solved in time 2^o(k) . n^O(1), even in the unit-weight setting. This lower bound makes Steiner Tree the first "genuinely planar" problem (i.e., where the input is only planar graph with a set of distinguished terminals) for which we can show that the square root phenomenon does not appear. • Steiner Tree can be solved in time n^O(sqrt(k)) * W on undirected planar graphs with maximum edge weight W. Note that this result is incomparable to the fact that the problem is known to be solvable in time 2^k . n^O(1) even in general graphs. A direct corollary of the combination of our results for Steiner Tree is that this problem does not admit a parameter-preserving polynomial kernel on planar graphs unless ETH fails.

In this paper, we study multi-budgeted variants of the classic minimum cut problem and graph separation problems that turned out to be important in parameterized complexity: Skew Multicut and Directed Feedback Arc Set. In our generalization, we assign colors 1,2,...,l to some edges and give separate budgets k_1,k_2,...,k_l for colors 1,2,...,l. For every color i in {1,...,l}, let E_i be the set of edges of color i. The solution C for the multi-budgeted variant of a graph separation problem not only needs to satisfy the usual separation requirements (i.e., be a cut, a skew multicut, or a directed feedback arc set, respectively), but also needs to satisfy that |C cap E_i| <= k_i for every i in {1,...,l}. Contrary to the classic minimum cut problem, the multi-budgeted variant turns out to be NP-hard even for l = 2. We propose FPT algorithms parameterized by k=k_1 +...+ k_l for all three problems. To this end, we develop a branching procedure for the multi-budgeted minimum cut problem that measures the progress of the algorithm not by reducing k as usual, by but elevating the capacity of some edges and thus increasing the size of maximum source-to-sink flow. Using the fact that a similar strategy is used to enumerate all important separators of a given size, we merge this process with the flow-guided branching and show an FPT bound on the number of (appropriately defined) important multi-budgeted separators. This allows us to extend our algorithm to the Skew Multicut and Directed Feedback Arc Set problems. Furthermore, we show connections of the multi-budgeted variants with weighted variants of the directed cut problems and the Chain l-SAT problem, whose parameterized complexity remains an open problem. We show that these problems admit a bounded-in-parameter number of "maximally pushed" solutions (in a similar spirit as important separators are maximally pushed), giving somewhat weak evidence towards their tractability.

Feedback Vertex Set is a classic combinatorial optimization problem that asks for a minimum set of vertices in a given graph whose deletion makes the graph acyclic. From the point of view of parameterized algorithms and fixed-parameter tractability, Feedback Vertex Set is one of the landmark problems: a long line of study resulted in multiple algorithmic approaches and deep understanding of the combinatorics of the problem. Because of its central role in parameterized complexity, the first edition of the Parameterized Algorithms and Computational Experiments Challenge (PACE) in 2016 featured Feedback Vertex Set as the problem of choice in one of its tracks. The results of PACE 2016 on one hand showed large discrepancy between performance of different classic approaches to the problem, and on the other hand indicated a new approach based on half-integral relaxations of the problem as probably the most efficient approach to the problem. In this paper we provide an exhaustive experimental evaluation of fixed-parameter and branching algorithms for Feedback Vertex Set.

Nie dotyczy

We study the problem of routing symmetric demand pairs in planar digraphs. The input consists of a directed planar graph $G=(V,E)$ and a collection of $k$ source-destination pairs $\mathcal{M} = \{s_1t_1, \dots, s_kt_k\}$. The goal is to maximize the number of pairs that are routed along disjoint paths. A pair $s_it_i$ is routed in the symmetric setting if there is a directed path connecting $s_i$ to $t_i$ and a directed path connecting $t_i$ to $s_i$. In this paper we obtain a randomized polylogarithmic approximation with constant congestion for this problem in planar digraphs. The main technical contribution is to show that a planar digraph with directed treewidth $h$ contains a relaxed cylindrical grid (which can serve as a constant congestion crossbar in the context of a routing algorithm) of size $\Omega(h/\mathrm{polylog}(h))$.

The Chordal Vertex Deletion (ChVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for ChVD under the parameterization by the solution size. Using a new Erdös--Pósa-type packing/covering duality for holes in nearly chordal graphs, we present a polynomial-time algorithm that reduces any instance $(G,k)$ of ChVD to an equivalent instance with ${poly}(k)$ vertices. The existence of a polynomial kernel answers an open problem posed by Marx in 2006 [D. Marx, “Chordal Deletion Is Fixed-Parameter Tractable,” in Graph-Theoretic Concepts in Computer Science, Lecture Notes in Comput. Sci. 4271, Springer, 2006, pp. 37--48]. To obtain the kernelization, we develop the first ${poly}({\sc opt})$-approximation algorithm for ChVD, which is of independent interest. In polynomial time, it either decides that $G$ has no chordal deletion set of size $k$, or outputs a solution of size $\mathcal{O}(k^4\log^2k)$.

In the I nterval C ompletion problem we are given an n -vertex graph G and an integer k , and the task is to transform G by making use of at most k edge additions into an interval graph. This is a fundamental graph modification problem with applications in sparse matrix multiplication and molecular biology. The question about fixed-parameter tractability of I nterval C ompletion was asked by Kaplan et al. [FOCS 1994; SIAM J. Comput. 1999] and was answered affirmatively more than a decade later by Villanger et al. [STOC 2007; SIAM J. Comput. 2009], who presented an algorithm with running time O ( k 2 k n 3 m ). We give the first subexponential parameterized algorithm solving I nterval C ompletion in time k O (√ k ) n O (1) . This adds I nterval C ompletion to a very small list of parameterized graph modification problems solvable in subexponential time.

In the M aximum W eight I ndependent S et problem, the input is a graph G , every vertex has a non-negative integer weight, and the task is to find a set S of pairwise nonadjacent vertices, maximizing the total weight of the vertices in S . We give an n O (log 2 n ) time algorithm for this problem on graphs excluding the path P 6 on 6 vertices as an induced subgraph. Currently, there is no constant k known for which M aximum W eight I ndependent S et on P k -free graphs becomes NP-hard, and our result implies that if such a k exists, then k > 6 unless all problems in NP can be decided in quasi-polynomial time. Using the combinatorial tools that we develop for this algorithm, we also give a polynomial-time algorithm for M aximum W eight E fficient D ominating S et on P 6 -free graphs. In this problem, the input is a graph G , every vertex has an integer weight, and the objective is to find a set S of maximum weight such that every vertex in G has exactly one vertex in S in its closed neighborhood or to determine that no such set exists. Prior to our work, the class of P 6 -free graphs was the only class of graphs defined by a single forbidden induced subgraph on which the computational complexity of M aximum W eight E fficient D ominating S et was unknown.

We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is a polynomial-time algorithm that, given an unweighted undirected graph G embedded on a surface of genus g and a designated face f bounded by a simple cycle of length k , uncovers a set F ⊆ E ( G ) of size polynomial in g and k that contains an optimal Steiner tree for any set of terminals that is a subset of the vertices of f . We apply this general theorem to prove that: — Given an unweighted graph G embedded on a surface of genus g and a terminal set S ⊆ V ( G ), one can in polynomial time find a set F ⊆ E ( G ) that contains an optimal Steiner tree T for S and that has size polynomial in g and | E ( T )|. — An analogous result holds for an optimal Steiner forest for a set S of terminal pairs. — Given an unweighted planar graph G and a terminal set S ⊆ V ( G ), one can in polynomial time find a set F ⊆ E ( G ) that contains an optimal (edge) multiway cut C separating S (i.e., a cutset that intersects any path with endpoints in different terminals from S ) and that has size polynomial in | C |. In the language of parameterized complexity, these results imply the first polynomial kernels for S teiner T ree and S teiner F orest on planar and bounded-genus graphs (parameterized by the size of the tree and forest, respectively) and for (E dge ) M ultiway C ut on planar graphs (parameterized by the size of the cutset). Additionally, we obtain a weighted variant of our main contribution: a polynomial-time algorithm that, given an undirected plane graph G with positive edge weights, a designated face f bounded by a simple cycle of weight w ( f ), and an accuracy parameter ε > 0, uncovers a set F ⊆ E ( G ) of total weight at most poly(ε -1 ) w ( f ) that, for any set of terminal pairs that lie on f , contains a Steiner forest within additive error ε w ( f ) from the optimal Steiner forest.

We show that for a number of parameterized problems for which only 2^{O(k)} n^{O(1)} time algorithms are known on general graphs, subexponential parameterized algorithms with running time 2^{O(k^{1-1/(1+d)} log^2 k)} n^{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 O(r^d) vertices. The algorithms use the technique of low-treewidth pattern covering, introduced by Fomin et al. [FOCS 2016] for planar graphs; here we show how this strategy can be made to work for graphs of 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 of V(G) such that on one hand the treewidth of G[A] is O(k^{1-1/(1+d)} log k), and on the other hand for every set X of vertices of size at most k, the probability that X is a subset of A is 2^{-O(k^{1-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 Long Path: unless the Exponential Time Hypothesis fails, no parameterized algorithm with running time 2^{k^{1-1/d-epsilon}}n^{O(1)} is possible for any positive epsilon and any integer d >= 3.

The notion of Turing kernelization investigates whether a polynomial-time algorithm can solve an NP-hard problem, when it is aided by an oracle that can be queried for the answers to bounded-size subproblems. One of the main open problems in this direction is whether k-PATH admits a polynomial Turing kernel: can a polynomial-time algorithm determine whether an undirected graph has a simple path of length k, using an oracle that answers queries of size k^{O(1)}? We show this can be done when the input graph avoids a fixed graph H as a topological minor, thereby significantly generalizing an earlier result for bounded-degree and K_{3,t}-minor-free graphs. Moreover, we show that k-PATH even admits a polynomial Turing kernel when the input graph is not H-topological-minor-free itself, but contains a known vertex modulator of size bounded polynomially in the parameter, whose deletion makes it so. To obtain our results, we build on the graph minors decomposition to show that any H-topological-minor-free graph that does not contain a k-path has a separation that can safely be reduced after communication with the oracle.

The Chordal Vertex Deletion (ChVD) problem asks to delete a minimum number of vertices from an input graph to obtain a chordal graph. In this paper we develop a polynomial kernel for ChVD under the parameterization by the solution size. Using a new Erdos-Posa type packing/covering duality for holes in nearly-chordal graphs, we present a polynomial-time algorithm that reduces any instance (G, k) of ChVD to an equivalent instance with poly(k) vertices. The existence of a polynomial kernel answers an open problem of Marx from 2006 [WG 2006, LNCS 4271, 37–48]. To obtain the kernelization, we develop the first poly(oPT)- approximation algorithm for ChVD, which is of independent interest. In polynomial time, it either decides that G has no chordal deletion set of size k, or outputs a solution of size O(k4 log2 k).

We study the complexity of a generic hitting problem H - Subgraph Hitting , where given a fixed pattern graph H and an input graph G , the task is to find a set X ⊆ V ( G ) of minimum size that hits all subgraphs of G isomorphic to H . In the colorful variant of the problem, each vertex of G is precolored with some color from V ( H ) and we require to hit only H -subgraphs with matching colors. Standard techniques shows that for every fixed H , the problem is fixed-parameter tractable parameterized by the treewidth of G ; however, it is not clear how exactly the running time should depend on treewidth. For the colorful variant, we demonstrate matching upper and lower bounds showing that the dependence of the running time on treewidth of G is tightly governed by μ ( H ) , the maximum size of a minimal vertex separator in H . That is, we show for every fixed H that, on a graph of treewidth t , the colorful problem can be solved in time 2 O ( t μ ( H ) ) ⋅ | V ( G ) | , but cannot be solved in time 2 o ( t μ ( H ) ) ⋅ | V ( G ) | O ( 1 ) , assuming the Exponential Time Hypothesis (ETH). Furthermore, we give some preliminary results showing that, in the absence of colors, the parameterized complexity landscape of H - Subgraph Hitting is much richer.

A graph is called {claw,diamond}-free if it contains neither a claw (a K 1,3) nor a diamond (a K 4 with an edge removed) as an induced subgraph. Equivalently, {claw,diamond}-free graphs are characterized as line graphs of triangle-free graphs, or as linear dominoes (graphs in which every vertex is in at most two maximal cliques and every edge is in exactly one maximal clique). We consider the parameterized complexity of the {claw,diamond}-free Edge Deletion problem, where given a graph G and a parameter k, the question is whether one can remove at most k edges from G to obtain a {claw,diamond}-free graph. Our main result is that this problem admits a polynomial kernel. We complement this result by proving that, even on instances with maximum degree 6, the problem is NP-complete and cannot be solved in time $2^{o(k)}\cdot |V(G)|^{\mathcal {O}(1)}$ unless the Exponential Time Hypothesis fails.

We give a fixed-parameter tractable algorithm that, given a parameter $k$ and two graphs $G_1,G_2$, either concludes that one of these graphs has treewidth at least $k$ or determines whether $G_1$ and $G_2$ are isomorphic. The running time of the algorithm on an $n$-vertex graph is $2^{\mathcal{O}(k^5\log k)}\cdot n^5$, and this is the first fixed-parameter algorithm for Graph Isomorphism parameterized by treewidth. Our algorithm in fact solves the more general canonization problem. We namely design a procedure working in $2^{\mathcal{O}(k^5\log k)}\cdot n^5$ time that, for a given graph $G$ on $n$ vertices, either concludes that the treewidth of $G$ is at least $k$ or (i) finds in an isomorphic-invariant way a graph $\mathfrak{c}(G)$ that is isomorphic to $G$; (ii) finds an isomorphism-invariant construction term---an algebraic expression that encodes $G$ together with a tree decomposition of $G$ of width less than $k$. Hence, the isomorphism test reduces to verifying whether the computed isomorphic copies or the construction terms for $G_1$ and $G_2$ are equal.

No abstract available.

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: 1) A induces a subgraph of G of treewidth O(√(k log k)), and 2) 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 log2 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 parameterized algorithms for problems on planar graphs, usually with running time bound 2O(√(k log2k))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 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.

In [Directed tree-width, J. Combin. Theory Ser. B 82 (2001), 138-154] we introduced the notion of tree-width of directed graphs and presented a conjecture, formulated during discussions with Noga Alon and Bruce Reed, stating that a digraph of huge tree-width has a large "cylindrical grid" minor. Here we prove the conjecture for planar digraphs, but many steps of the proof work in general. This is an unedited and unpolished manuscript from October 2001. Since many people asked for copies we are making it available in the hope that it may be useful. The conjecture was proved by Kawarabayashi and Kreutzer in arXiv:1411.5681.

In the EDGE BIPARTIZATION problem one is given an undirected graph G and an integer k, and the question is whether k edges can be deleted from G so that it becomes bipartite. In 2006, Guo et al. [J. Comput. Syst. Sci., 72(8):1386-1396, 2006] proposed an algorithm solving this problem in time O(2^k m^2); today, this algorithm is a textbook example of an application of the iterative compression technique. Despite extensive progress in the understanding of the parameterized complexity of graph separation problems in the recent years, no significant improvement upon this result has been yet reported. We present an algorithm for Edge Bipartization that works in time O(1.977^k nm), which is the first algorithm with the running time dependence on the parameter better than 2^k. To this end, we combine the general iterative compression strategy of Guo et al. [J. Comput. Syst. Sci., 72(8):1386-1396, 2006], the technique proposed by Wahlström [SODA'14] of using a polynomial-time solvable relaxation in the form of a Valued Constraint Satisfaction Problem to guide a bounded-depth branching algorithm, and an involved Measure&Conquer analysis of the recursion tree.

In the Interval Completion problem we are given an n-vertex graph G and an integer k, and the task is to transform G by making use of at most k edge additions into an interval graph. This is a fundamental graph modification problem with applications in sparse matrix multiplication and molecular biology. The question about fixed-parameter tractability of Interval Completion was asked by Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999] and was answered affirmatively more than a decade later by Villanger at el. [STOC 2007; SIAM J. Comput. 2009], who presented an algorithm with running time O(k2kn3m). We give the first subexponential parameterized algorithm solving Interval Completion in time . This adds Interval Completion to a very small list of parameterized graph modification problems solvable in subexponential time.

In the Maximum Weight Independent Set problem, the input is a graph G, every vertex has a nonnegative integer weight, and the task is to find a set S of pairwise non-adjacent vertices, maximizing the total weight of the vertices in S. We give an time algorithm for this problem on graphs excluding the path P6 on 6 vertices as an induced subgraph. Currently, there is no constant k known for which Maximum Weight Independent Set on Pk-free graphs becomes NP-complete, and our result implies that if such a k exists, then k > 6 unless all problems in NP can be decided in (quasi)polynomial time. Using the combinatorial tools that we develop for the above algorithm, we also give a polynomial-time algorithm for Maximum Weight Efficient Dominating Set on P6-free graphs. In this problem, the input is a graph G, every vertex has an integer weight, and the objective is to find a set S of maximum weight such that every vertex in G has exactly one vertex in S in its closed neighborhood, or to determine that no such set exists. Prior to our work, the class of P6-free graphs was the only class of graphs defined by a single forbidden induced subgraph on which the computational complexity of Maximum Weight Efficient Dominating Set was unknown.

We prove that Multicut in directed graphs, parameterized by the size of the cutset, is W[1]-hard and hence unlikely to be fixed-parameter tractable even if restricted to instances with only four terminal pairs. This negative result almost completely resolves one of the central open problems in the area of parameterized complexity of graph separation problems, posted originally by Marx and Razgon [SIAM J. Comput. 43(2):355–388 (2014)], leaving only the case of three terminal pairs open. The case of two terminal pairs was shown to be FPT by Chitnis et al. [SIAM J. Comput. 42(4):1674–1696 (2013)]. Our gadget methodology also allows us to prove W[1]-hardness of the Steiner Orientation problem parameterized by the number of terminal pairs, resolving an open problem of Cygan, Kortsarz, and Nutov [SIAM J. Discrete Math. 27(3):1503–1513 (2013)].

In the family of clustering problems we are given a set of objects (vertices of the graph), together with some observed pairwise similarities (edges). The goal is to identify clusters of similar objects by slightly modifying the graph to obtain a cluster graph (disjoint union of cliques). Hüffner et al. (Theory Comput. Syst. 47(1), 196–217, 2010) initiated the parameterized study of Cluster Vertex Deletion, where the allowed modification is vertex deletion, and presented an elegant $\mathcal {O}\left (\min (2^{k} k^{6} \log k + n^{3}, 2^{k} km\sqrt {n} \log n)\right )$ -time fixed-parameter algorithm, parameterized by the solution size. In the last 5 years, this algorithm remained the fastest known algorithm for Cluster Vertex Deletion and, thanks to its simplicity, became one of the textbook examples of an application of the iterative compression principle. In our work we break the 2 k -barrier for Cluster Vertex Deletion and present an $\mathcal {O}(1.9102^{k} (n+m))$ -time branching algorithm. We achieve this improvement by a number of structural observations which we incorporate into the algorithm’s branching steps.

We introduce a new technique for designing fixed-parameter algorithms for cut problems, called randomized contractions. We apply our framework to obtain the first fixed-parameter algorithms (FPT algorithms) with exponential speed up for the Steiner Cut and Node Multiway Cut-Uncut problems. We prove that the parameterized version of the Unique Label Cover problem, which is the base of the Unique Games Conjecture, can be solved in $2^{O(k^2\log |\Sigma|)}n^4\log n$ deterministic time (even in the stronger, vertex-deletion variant), where $k$ is the number of unsatisfied edges and $|\Sigma|$ is the size of the alphabet. As a consequence, we show that one can in polynomial time solve instances of Unique Games where the number of edges allowed not to be satisfied is upper bounded by $O(\sqrt{\log n})$ to optimality, which improves over the trivial $O(1)$ upper bound. We prove that the Steiner Cut problem can be solved in $2^{O(k^2\log k)}n^4\log n$ deterministic time and $\tilde{O}(2^{O(k^2\log k)}n^2)$ randomized time, where $k$ is the size of the cutset. This result improves the double exponential running time of the recent work of Kawarabayashi and Thorup presented at FOCS'11. We show how to combine considering “cut” and “uncut” constraints at the same time. More precisely, we define a robust problem, Node Multiway Cut-Uncut, that can serve as an abstraction of introducing uncut constraints and show that it admits an algorithm running in $2^{O(k^2\log k)}n^4\log n$ deterministic time, where $k$ is the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan, and Razgon [ACM Trans. Algorithms, 9 (2013), 30], which yields algorithms with double exponential running time. An interesting aspect of our algorithms is that they can handle positive real weights.

In the Edge Clique Cover (ECC) problem, given an undirected graph $G$ and an integer $k$, we ask whether one can choose $k$ cliques in $G$ such that each edge of $G$ is contained in at least one of the chosen cliques. Gramm et al. [ACM J. Exp. Algorithmics, 13 (2008)] have shown a set of simple rules that reduce the number of vertices of $G$ to $2^k$ while preserving the answer to the instance at hand, that is, they have shown a kernel for the problem with at most $2^k$ vertices. No algorithm is known with significantly better running time bound than a brute-force search on this kernel. 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 instance of $3$-CNF-SAT with $n$ variables and $m$ clauses to an equivalent ECC instance $(G,k)$ with $k = \mathcal{O}(\log n)$ and $|V(G)| = \mathcal{O}(n + m)$. Consequently, there is no $2^{2^{o(k)}}{\rm poly}(n)$ time algorithm for the ECC problem, unless the Exponential Time Hypothesis fails. Moreover, our reduction also implies that, unless P $ = $ NP, the ECC problem does not admit a subexponential kernel, i.e., a kernel of size $2^{o(k)}$.

In this paper we study the Steiner tree problem over a dynamic set of terminals. We consider the model where we are given an n-vertex graph G=(V,E,w) with positive real edge weights, and our goal is to maintain a tree which is a good approximation of the minimum Steiner tree spanning a terminal set S ⊆ V, which changes over time. The changes applied to the terminal set are either terminal additions (incremental scenario), terminal removals (decremental scenario), or both (fully dynamic scenario). Our task here is twofold. We want to support updates in sublinear o(n) time, and keep the approximation factor of the algorithm as small as possible.

We present a number of exponential-time algorithms for problems in sparse matrices and graphs of bounded average degree. First, we obtain a simple algorithm that computes a permanent of an n × n matrix over an arbitrary commutative ring with at most dn non-zero entries using O ⋆ ( 2 ( 1 − 1 / ( 3.55 d ) ) n ) time and ring operations, 1 improving and simplifying the recent result of Izumi and Wadayama [FOCS 2012]. Second, we present a simple algorithm for counting perfect matchings in an n -vertex graph in O ⋆ ( 2 n / 2 ) time and polynomial space; our algorithm matches the complexity bounds of the algorithm of Björklund [SODA 2012], but relies on inclusion–exclusion principle instead of algebraic transformations. Third, we show a combinatorial lemma that bounds the number of “Hamiltonian-like” structures in a graph of bounded average degree. Using this result, we show that 1. a minimum weight Hamiltonian cycle in an n -vertex graph with average degree bounded by d can be found in O ⋆ ( 2 ( 1 − ε d ) n ) time and exponential space for a constant ε d depending only on d ; 2. the number of perfect matchings in an n -vertex graph with average degree bounded by d can be computed in O ⋆ ( 2 ( 1 − ε d ′ ) n / 2 ) time and exponential space, for a constant ε d ′ depending only on d . The algorithm for minimum weight Hamiltonian cycle generalizes the recent results of Björklund et al. [TALG 2012] on graphs of bounded degree.

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 (2011) initiated the study of the problem of appropriately visualising the network: They asked whether any signed graph can be embedded into the metric space ${{\mathbb {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 ${{\mathbb {R}}}^{1}$ can be expressed as a purely combinatorial problem. In this paper we pursue a deeper study of this 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.

In the Proper Interval Completion problem we are given a graph $G$ and an integer $k$, and the task is to turn $G$ using at most $k$ edge additions into a proper interval graph, i.e., a graph admitting an intersection model of equal-length intervals on a line. The study of Proper Interval Completion from the viewpoint of parameterized complexity has been initiated by Kaplan, Shamir, and Tarjan [SIAM J. Comput., 28 (1999), pp. 1906--1922], who showed an algorithm for the problem working in $\mathcal{O}(16^k\cdot (n+m))$ time. In this paper we present an algorithm with running time $k^{\mathcal{O}(k^{2/3})} + \mathcal{O}(nm(kn+m))$, which is the first subexponential parameterized algorithm for Proper Interval Completion.

The Multicut problem, given a graph G, a set of terminal pairs $\mathcal{T}=\{(s_i,t_i)\ |\ 1\leq i\leq r\}$, and an integer $p$, asks whether one can find a cutset consisting of at most $p$ nonterminal vertices that separates all the terminal pairs, i.e., after removing the cutset, $t_i$ is not reachable from $s_i$ for each $1\leq i\leq r$. The fixed-parameter tractability of Multicut in undirected graphs, parameterized by the size of the cutset only, has been recently proved by Marx and Razgon [SIAM J. Comput., 43 (2014), pp. 355--388] and, independently, by Bousquet, Daligault, and Thomassé [Proceedings of STOC, ACM, 2011, pp. 459--468], after resisting attacks as a long-standing open problem. In this paper we prove that Multicut is fixed-parameter tractable on directed acyclic graphs when parameterized both by the size of the cutset and the number of terminal pairs. We complement this result by showing that this is implausible for parameterization by the size of the cutset only, as this version of the problem remains $W[1]$-hard.

We give a fixed-parameter tractable algorithm that, given a parameter k and two graphs G1, G2, either concludes that one of these graphs has treewidth at least k, or determines whether G1and G2are isomorphic. The running time of the algorithm on an n-vertex graph is 2O(k5 log k)· n5, and this is the first fixed-parameter algorithm for Graph Isomorphism parameterized by treewidth. Our algorithm in fact solves the more general canonization problem. We namely design a procedure working in 2OO(k5 log k)· n5time that, for a given graph G on n vertices, either concludes that the treewidth of G is at least k, or finds an isomorphism-invariant construction term - an algebraic expression that encodes G together with a tree decomposition of G of width O(k4). Hence, a canonical graph isomorphic to G can be constructed by simply evaluating the obtained construction term, while the isomorphism test reduces to verifying whether the computed construction terms for G1and G2are equal.

We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is a polynomial-time algorithm that, given an unweighted graph G embedded on a surface of genus g and a designated face f bounded by a simple cycle of length k, uncovers a set F in E(G) of size polynomial in g and k that contains an optimal Steiner tree for any set of terminals that is a subset of the vertices of f. We apply this general theorem to prove that: (2) given an unweighted graph G embedded on a surface of genus g and a terminal set S in V(G), one can in polynomial time find a set F in E(G) that contains an optimal Steiner tree T for S and that has size polynomial in g and |E(T)|; (2) an analogous result holds for an optimal Steiner forest for a set S of terminal pairs, (3) given an unweighted planar graph G and a terminal set S in V(G), one can in polynomial time find a set F in E(G) that contains an optimal (edge) multiway cut C separating S (i.e., a cutset that intersects any path with endpoints in different terminals from S) and has size polynomial in |C|. In the language of parameterized complexity, these results imply the first polynomial kernels for Steiner Tree and Steiner Forest on planar and bounded-genus graphs (parameterized by the size of the tree and forest, respectively) and for (Edge) Multiway Cut on planar graphs (parameterized by the size of the cutset). Steiner Tree and similar "subset" problems were identified in [Demaine, Hajiaghayi, Computer J., 2008] as important to the quest to widen the reach of the theory of bidimensionality ([Demaine et al., JACM 2005], [Fomin et al., SODA 2010]). Therefore, our results can be seen as a leap forward to achieve this broader goal. Additionally, we obtain a weighted variant of our main contribution: a polynomial-time algorithm that, given an edge-weighted planar graph G, a designated face f bounded by a simple cycle of weight w(f), and an accuracy parameter ε > 0, uncovers a set F in E(G) of total weight at most poly(1/ε) w(f) that, for any set of terminal pairs that lie on f, contains a Steiner forest within additive error ε w(f) from the optimal Steiner forest. This result deepens the understanding of the recent framework of approximation schemes for network design problems on planar graphs ([Klein, SICOMP 2008], [Borradaile, Klein, Mathieu, ACM TALG 2009], and later works) by explaining the structure of the solution space within a brick of the so-called mortar graph -- the central notion of this framework.

In the classic Minimum Bisection problem we are given as input a graph G and an integer k. The task is to determine whether there is a partition of V (G) into two parts A and B such that ||A| -- |B|| ≤ 1 and there are at most k edges with one endpoint in A and the other in B. In this paper we give an algorithm for Minimum Bisection with running time O(2O(k3) n3 log3 n). This is the first fixed parameter tractable algorithm for Minimum Bisection. At the core of our algorithm lies a new decomposition theorem that states that every graph G can be decomposed by small separators into parts where each part is "highly connected" in the following sense: any cut of bounded size can separate only a limited number of vertices from each part of the decomposition.

We study the Cutwidth problem, where the input is a graph G, and the objective is find a linear layout of the vertices that minimizes the maximum number of edges intersected by any vertical line inserted between two consecutive vertices. We give an algorithm for Cutwidth with running time O(2 k n O(1)). Here k is the size of a minimum vertex cover of the input graph G, and n is the number of vertices in G. Our algorithm gives an O(2 n/2 n O(1)) time algorithm for Cutwidth on bipartite graphs as a corollary. This is the first non-trivial exact exponential time algorithm for Cutwidth on a graph class where the problem remains NP-complete. Additionally, we show that Cutwidth parameterized by the size of the minimum vertex cover of the input graph does not admit a polynomial kernel unless NP⊆coNP/poly. Our kernelization lower bound contrasts with the recent results of Bodlaender et al. (ICALP, Springer, Berlin, 2011; SWAT, Springer, Berlin, 2012) that both Treewidth and Pathwidth parameterized by vertex cover do admit polynomial kernels.

We study a family of problems where the goal is to make a graph Eulerian, i.e., connected and with all the vertices having even degrees, by a minimum number of deletions. We completely classify the parameterized complexity of various versions: undirected or directed graphs, vertex or edge deletions, with or without the requirement of connectivity, etc. The collection of results shows an interesting contrast: while the node-deletion variants remain intractable, i.e., W[1]-hard for all the studied cases, edge-deletion problems are either fixed-parameter tractable or polynomial-time solvable. Of particular interest is a randomized FPT algorithm for making an undirected graph Eulerian by deleting the minimum number of edges, based on a novel application of the color coding technique. For versions that remain NP-complete but fixed-parameter tractable we consider also possibilities of polynomial kernelization; unfortunately, we prove that this is not possible unless NP⊆coNP/poly.

In a scheduling problem, denoted by 1|prec|∑C i in the Graham notation, we are given a set of n jobs, together with their processing times and precedence constraints. The task is to order the jobs so that their total completion time is minimized. 1|prec|∑C i is a special case of the Traveling Repairman Problem with precedences. A natural dynamic programming algorithm solves both these problems in 2 n n O(1) time, and whether there exists an algorithms solving 1|prec|∑C i in O(c n ) time for some constant c<2 was an open problem posted in 2004 by Woeginger. In this paper we answer this question positively.

The 2-Disjoint Connected Subgraphs problem, given a graph along with two disjoint sets of terminals Z 1,Z 2, asks whether it is possible to find disjoint sets A 1,A 2, such that Z 1⊆A 1, Z 2⊆A 2 and A 1,A 2 induce connected subgraphs. While the naive algorithm runs in O(2 n n O(1)) time, solutions with complexity of form O((2−ε) n ) have been found only for special graph classes (van ’t Hof et al. in Theor. Comput. Sci. 410(47–49):4834–4843, 2009; Paulusma and van Rooij in Theor. Comput. Sci. 412(48):6761–6769, 2011). In this paper we present an O(1.933 n ) algorithm for 2-Disjoint Connected Subgraphs in general case, thus breaking the 2 n barrier. As a counterpoise of this result we show that if we parameterize the problem by the number of non-terminal vertices, it is hard both to speed up the brute-force approach and to find a polynomial kernel.

Given a graph G and k pairs of vertices (s1, t1), ..., (sk, tk), the k-Vertex-Disjoint Paths problem asks for pair wise vertex-disjoint paths P1, ..., Pk such that Pi goes from si to ti. Schrijver [SICOMP'94] proved that the k-Vertex-Disjoint Paths problem on planar directed graphs can be solved in timenO(k). We give an algorithm with running time 22O(k2)* nO(1)for the problem, that is, we show the fixed-parameter tractability of the problem.

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 2k, 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 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.

In the Correlation Clustering problem, also known as Cluster Editing, we are given an undirected graph G and a positive integer k; the task is to decide whether G can be transformed into a cluster graph, i.e., a disjoint union of cliques, by changing at most k adjacencies, that is, by adding or deleting at most k edges. The motivation of the problem stems from various tasks in computational biology (Ben-Dor et al., Journal of Computational Biology 1999) and machine learning (Bansal et al., Machine Learning 2004). Although in general Correlation Clustering is APX-hard (Charikar et al., FOCS 2003), the version of the problem where the number of cliques may not exceed a prescribed constant p admits a PTAS (Giotis and Guruswami, SODA 2006). We study the parameterized complexity of Correlation Clustering with this restriction on the number of cliques to be created. We give an algorithm that - in time O(2^{O(sqrt{pk})} + n+m) decides whether a graph G on n vertices and m edges can be transformed into a cluster graph with exactly p cliques by changing at most k adjacencies. We complement these algorithmic findings by the following, surprisingly tight lower bound on the asymptotic behavior of our algorithm. We show that unless the Exponential Time Hypothesis (ETH) fails - for any constant 0 <= sigma <= 1, there is p = Theta(k^sigma) such that there is no algorithm deciding in time 2^{o(sqrt{pk})} n^{O(1)} whether an n-vertex graph G can be transformed into a cluster graph with at most p cliques by changing at most k adjacencies. Thus, our upper and lower bounds provide an asymptotically tight analysis of the multivariate parameterized complexity of the problem for the whole range of values of p from constant to a linear function of k.

The well-known bidimensionality theory provides a method for designing fast, subexponential-time parameterized algorithms for a vast number of NP-hard problems on sparse graph classes such as planar graphs, bounded genus graphs, or, more generally, graphs with a fixed excluded minor. However, in order to apply the bidimensionality framework the considered problem needs to fulfill a special density property. Some well-known problems do not have this property, unfortunately, with probably the most prominent and important example being the Steiner Tree problem. Hence the question whether a subexponential-time parameterized algorithm for Steiner Tree on planar graphs exists has remained open. In this paper, we answer this question positively and develop an algorithm running in O(2^{O((k log k)^{2/3})}n) time and polynomial space, where k is the size of the Steiner tree and n is the number of vertices of the graph. Our algorithm does not rely on tools from bidimensionality theory or graph minors theory, apart from Baker's classical approach. Instead, we introduce new tools and concepts to the study of the parameterized complexity of problems on sparse graphs.

The classical Feedback Vertex Set problem asks, for a given undirected graph $G$ and an integer $k$, to find a set of at most $k$ vertices that hits all the cycles in the graph $G$. Feedback Vertex Set has attracted a large amount of research in the parameterized setting, and subsequent fixed-parameter and kernelization algorithms have been a rich source of ideas in the field. In this paper we consider a more general and difficult version of the problem, named Subset Feedback Vertex Set (Subset-FVS), where an instance comes additionally with a set $S \subseteq V$ of vertices, and we ask for a set of at most $k$ vertices that hits all simple cycles passing through $S$. Because of its applications in circuit testing and genetic linkage analysis, Subset-FVS was studied from the approximation algorithm perspective by Even et al. [SIAM J. Discrete Math., 13 (2000), pp. 225--267; SIAM J. Comput., 30 (2000), pp. 1231--1252]. The question of whether the Subset-FVS problem is fixed-parameter tractable was posed independently by Kawarabayashi and Saurabh in 2009. We answer this question affirmatively. We begin by showing that this problem is fixed-parameter tractable when parameterized by $|S|$. Next we present an algorithm which reduces the given instance to $2^k n^{O(1)}$ instances with the size of $S$ bounded by $O(k^3)$, using kernelization techniques such as the $2$-expansion lemma, Menger's theorem, and Gallai's theorem. These two facts allow us to give a $2^{O(k\log k)} n^{O(1)}$ time algorithm solving the Subset-FVS problem, proving that it is indeed fixed-parameter tractable.

We introduce a new technique for designing fixed-parameter algorithms for cut problems, namely randomized contractions. With our framework: (1) We obtain the first FPT algorithm for the parameterized version of the UNIQUE LABEL COVER problem, with single exponential dependency on the size of the cutset and the size of the alphabet. As a consequence, we extend the set of the polynomial time solvable instances of UNIQUE GAMES to those with at most O(√{log n}) violated constraints. (2) We obtain a new FPT algorithm for the STEINER CUT problem with exponential speed-up over the recent work of Kawarabayashi and Thorup (FOCS'11). (3) We show how to combine considering 'cut' and 'uncut' constraints at the same time. We define a robust problem NODE MULTIWAY CUT-UNCUT that can serve as an abstraction of introducing uncut constraints, and show that it admits an FPT algorithm with single exponential dependency on the size of the cutset. To the best of our knowledge, the only known way of tackling uncut constraints was via the approach of Marx, O'Sullivan and Razgon (STACS'10), which yields algorithms with double exponential running time. An interesting aspect of our algorithms is that they can handle real weights, to the best of our knowledge, the technique of important separators does not work in the weighted version.

The Pathwidth One Vertex Deletion (POVD) problem asks whether, given an undirected graph G and an integer k, one can delete at most k vertices from G so that the remaining graph has pathwidth at most 1. The question can be considered as a natural variation of the extensively studied Feedback Vertex Set (FVS) problem, where the deletion of at most k vertices has to result in the remaining graph having treewidth at most 1 (i.e., being a forest). Recently Philip et al. (WG, Lecture Notes in Computer Science, vol. 6410, pp. 196–207, 2010) initiated the study of the parameterized complexity of POVD, showing a quartic kernel and an algorithm which runs in time 7 k n O(1). In this article we improve these results by showing a quadratic kernel and an algorithm with time complexity 4.65 k n O(1), thus obtaining almost tight kernelization bounds when compared to the general result of Dell and van Melkebeek (STOC, pp. 251–260, ACM, New York, 2010). Techniques used in the kernelization are based on the quadratic kernel for FVS, due to Thomassé (ACM Trans. Algorithms 6(2), 2010).

One of the driving problems in the CSP area is the dichotomy conjecture, formulated in 1993 by Feder and Vardi [Monotone monadic SNP and constraint satisfaction, in Proceedings of the 25th Annual Symposium on Theory of Computing, ACM, New York, 1993, pp. 612--622], stating that for any fixed relational structure $\Gamma$ the constraint satisfaction problem CSP($\Gamma$) is either NP-complete or polynomial time solvable. A large amount of research has gone into checking various specific cases of this conjecture. One such variant which attracted a lot of attention in recent years is the List Matrix Partition problem. In 2004 Cameron et al. [SIAM J. Discrete Math., 21 (2007), pp. 900--929] classified almost all List Matrix Partition variants for matrices of size at most four. The only case which resisted the classification became known as the Stubborn problem. In this paper we show a result which enables us to finish the classification---thus solving a problem which resisted attacks for a few years. Our approach is based on a combinatorial problem known to be at least as hard as the Stubborn problem---the 3-Compatible Coloring problem. In this problem we are given a complete graph with each edge assigned one of three possible colors and we want to assign one of those three colors to each vertex in such a way that no edge has the same color as both of its endpoints. The tractability of the 3-Compatible Coloring problem has been open for several years and the best known algorithm prior to this paper is due to Feder et al. [Two algorithms for general list matrix partitions, in Proceedings of the 16th Annual ACM-SIAM Symposium on Discrete Algorithms, ACM, New York, SIAM, Philadelphia, 2005, pp. 870--876]---a quasipolynomial algorithm with a $n^{O(\log n / \log \log n)}$ time complexity. In this paper we present a polynomial-time algorithm for the 3-Compatible Coloring problem and consequently we prove a dichotomy for the k-Compatible Coloring problem.

We deal with exact algorithms for Bandwidth , a long studied NP-hard problem. For a long time nothing better than the trivial O * ( n !) 1 exhaustive search was known. In 2000, Feige and Kilian [Feige 2000] came up with a O * (10 n )-time and polynomial space algorithm. In this article we present a new algorithm that solves Bandwidth in O * (5 n ) time and O * (2 n ) space. Then, we take a closer look and introduce a major modification that makes it run in O (4.83 n ) time with a cost of a O * (4 n ) space complexity. This modification allowed us to perform the Measure & Conquer analysis for the time complexity which was not used for graph layout problems before.

For the vast majority of local problems on graphs of small tree width (where by local we mean that a solution can be verified by checking separately the neighbourhood of each vertex), standard dynamic programming techniques give c^tw |V|^O(1) time algorithms, where tw is the tree width 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 tw^tw time. We breach this gap by introducing a technique we named Cut&Count that allows to produce c^tw |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-minor-free 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 contrast to the problems aiming to minimize 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 breached for some problems that aim to maximize the number of connected components like Cycle Packing.

In a classical covering problem, we are given a set of requests that we need to satisfy (fully or partially), by buying a subset of items at minimum cost. For example, in the k-MST problem we want to find the cheapest tree spanning at least k nodes of an edge-weighted graph. Here, nodes represent requests whereas edges correspond to items. In this paper, we initiate the study of a new family of multi-layer covering problems. Each such problem consists of a collection of h distinct instances of a standard covering problem (layers), with the constraint that all layers share the same set of requests. We identify two main subfamilies of these problems: - in an union multi-layer problem, a request is satisfied if it is satisfied in at least one layer; - in an intersection multi-layer problem, a request is satisfied if it is satisfied in all layers. To see some natural applications, consider both generalizations of k-MST. Union k-MST can model a problem where we are asked to connect a set of users to at least one of two communication networks, e.g., a wireless and a wired network. On the other hand, Intersection k-MST can formalize the problem of providing both electricity and water to at least k users.

We present a polynomial time algorithm for the 3-Compatible colouring problem, where we are given a complete graph with each edge assigned one of 3 possible colours and we want to assign one of those 3 colours to each vertex in such a way that no edge has the same colour as both of its endpoints. Consequently we complete the proof of a dichotomy for the k-Compatible Colouring problem. The tractability of the 3-Compatible colouring problem has been open for several years and the best known algorithm prior to this paper is due to Feder et al. [SODA'05] — a quasipolynomial algorithm with a nO(log n/log log n) time complexity. Furthermore our result implies a polynomial algorithm for the Stubborn problem which enables us to finish the classification of all List Matrix Partition variants for matrices of size at most four over subsets of {0, 1} started by Cameron et al. [SODA'04].