Matroids, particularly linear matroids, have been a powerful tool for applications in parameterized complexity, both for algorithms and kernelization. In particular, they have been instrumental in speeding up or replacing dynamic programming. Delta-matroids are a generalization of matroids that further encapsulate structures such as non-maximum matchings in general graphs and various path-packing and topological structures. There is also a notion of linear delta-matroids (represented by skew-symmetric matrices) which carries significant expressive power and enables powerful algorithms. We investigate parameterized complexity aspects of problems defined over linear delta-matroids, or with delta-matroid constraints. Our initial analysis of basic intersection and packing problems reveals a different complexity landscape compared to the more familiar matroid case. In particular, there is a stark contrast in complexity between the cardinality parameter k and the rank parameter r. For example, finding an intersection of size k of three linear delta-matroids is W[1]-hard when parameterized by k, while far more general problems (such as finding a set packing of size k that is feasible in a given linear delta-matroid) are FPT when parameterized by the rank r of the delta-matroid. In fact, we extend the recent determinantal sieving procedure of Eiben, Koana, and Wahlström (TheoretiCS 2025) into a process that sieves a given polynomial for a monomial whose support is feasible in a given linear delta-matroid, parameterized by r. This is a direct generalization of determinantal sieving. Second, we investigate a curious class of problems that turns out to be FPT parameterized by k, even on delta-matroids of unbounded rank. We begin with Delta-matroid Triangle Cover - find a feasible set of size k that can be covered by a vertex-disjoint packing of triangles (i.e., sets of size 3) out of a given triangle collection. For example, this allows us to find, in a graph, a packing of K₃’s and K₂’s with the maximum possible number of edges, parameterized above the matching number of the graph (note that this problem is NP-hard, unlike the problem of finding such a packing covering a maximum number of vertices, which is tractable). As applications, we resolve the FPT status of Cluster Subgraph and Strong Triadic Closure parameterized above the matching number.

We consider the Min-r-Lin(ℤ_m) problem: given a system S of length-r linear equations modulo m, find Z ⊆ S of minimum cardinality such that S-Z is satisfiable. The problem is NP-hard and UGC-hard to approximate in polynomial time within any constant factor even when r = m = 2. We focus on parameterized approximation with solution size as the parameter. Dabrowski, Jonsson, Ordyniak, Osipov and Wahlström [SODA-2023] showed that Min-r-Lin(ℤ_m) is in FPT if m is prime (i.e. ℤ_m is a field), and it is W[1]-hard if m is not a prime power. We show that Min-r-Lin(ℤ_{pⁿ}) is FPT-approximable within a factor of 2 for every prime p and integer n ≥ 2. This implies that Min-2-Lin(ℤ_m), m ∈ ℤ^+, is FPT-approximable within a factor of 2ω(m) where ω(m) counts the number of distinct prime divisors of m. The high-level idea behind the algorithm is to solve tighter and tighter relaxations of the problem, decreasing the set of possible values for the variables at each step. When working over ℤ_{pⁿ} and viewing the values in base-p, one can roughly think of a relaxation as fixing the number of trailing zeros and the least significant nonzero digits of the values assigned to the variables. To solve the relaxed problem, we construct a certain graph where solutions can be identified with a particular collection of cuts. The relaxation may hide obstructions that will only become visible in the next iteration of the algorithm, which makes it difficult to find optimal solutions. To deal with this, we use a strategy based on shadow removal [Marx & Razgon, STOC-2011] to compute solutions that (1) cost at most twice as much as the optimum and (2) allow us to reduce the set of values for all variables simultaneously. We complement the algorithmic result with two lower bounds, ruling out constant-factor FPT-approximation for Min-3-Lin(R) over any nontrivial ring R and for Min-2-Lin(R) over some finite commutative rings R.

Given a graph G and an integer k, the H-free Edge Deletion problem asks whether there exists a set of at most k edges of G whose deletion makes G free of induced copies of H. Significant attention has been given to the kernelizability aspects of this problem - i.e., for which graphs H does the problem admit an "efficient preprocessing" procedure, known as a polynomial kernelization, where an instance I of the problem with parameter k is reduced to an equivalent instance I' whose size and parameter value are bounded polynomially in k? Although such routines are known for many graphs H where the class of H-free graphs has significant restricted structure, it is also clear that for most graphs H the problem is incompressible, i.e., admits no polynomial kernelization parameterized by k unless the polynomial hierarchy collapses. These results led Marx and Sandeep to the conjecture that H-free Edge Deletion is incompressible for any graph H with at least five vertices, unless H is complete or has at most one edge (JCSS 2022). This conjecture was reduced to the incompressibility of H-free Edge Deletion for a finite list of graphs H. We consider one of these graphs, which we dub the prison, and show that Prison-Free Edge Deletion has a polynomial kernel, refuting the conjecture. On the other hand, the same problem for the complement of the prison is incompressible.

We present new algorithms and constructions for linear delta-matroids. Delta-matroids are generalizations of matroids that also capture structures such as matchable vertex sets in graphs and path-packing problems. As with matroids, an important class of delta-matroids is given by linear delta-matroids, which generalize linear matroids and are represented via a "twist" of a skew-symmetric matrix. We observe an alternative representation, termed a contraction representation over a skew-symmetric matrix. This representation is equivalent to the more standard twist representation up to O(n^ω)-time transformations (where n is the dimension of the delta-matroid and ω < 2.372 the matrix multiplication exponent), but it is much more convenient for algorithmic tasks. For instance, the problem of finding a max-weight feasible set now reduces directly to finding a max-weight basis in a linear matroid. Supported by this representation, we provide new algorithms and constructions for linear delta-matroids. In particular, we show that the union and delta-sum of linear delta-matroids are again linear delta-matroids, and that a representation for the resulting delta-matroid can be constructed in randomized time O(n^ω) (or more precisely, in O(n^ω) field operations, over a field of size at least Ω(n⋅(1/ε)), where ε > 0 is an error parameter). Previously, it was only known that these operations define delta-matroids. We also note that every projected linear delta-matroid can be represented as an elementary projection. This implies that several optimization problems over (projected) linear delta-matroids, including the coverage, delta-coverage, and parity problems, reduce (in their decision versions) to a single O(n^ω)-time matrix rank computation. Using the methods of Harvey, previously applied by Cheung, Lao and Leung for linear matroid parity, we furthermore show how to solve the search versions in the same time. This improves on the O(n⁴)-time augmenting path algorithm of Geelen, Iwata and Murota, albeit with randomization. Finally, we consider the maximum-cardinality delta-matroid intersection problem (equivalently, the maximum-cardinality delta-matroid matching problem). Using Storjohann’s algorithms for symbolic determinants, we show that such a solution can be found in O(n^{ω+1}) time. This provides the first (randomized) polynomial-time solution for the problem, thereby solving an open question of Kakimura and Takamatsu.

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

Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimises the number of unsatisfied equations. This problem is NP-hard and UGC-hard to approximate within any constant even for two-variable equations over the two-element field. We study this problem from the point of view of parameterized complexity, with the parameter being the number of unsatisfied equations. We consider equations defined over a family of commutative domains (i.e. rings without zero divisors) with a particular Helly property. This set contains, for instance, finite and infinite fields, the ring of integers and univariate polynomial rings with coefficients from a field; more generally, it contains the important class of Prüfer domains. We show that if every equation contains at most two variables, the problem is fixed-parameter tractable. This generalises many eminent graph separation problems such as Bipartization, Multiway Cut and Multicut parameterized by the size of the cutset. To complement this, we show that the problem is W[1]-hard when three or more variables are allowed in an equation, as well as for many commutative rings that are not covered by our fpt result. On the technical side, we introduce the notion of important balanced subgraphs, generalising the important separators of Marx to the setting of biased graphs. Furthermore, we use recent results of Kim, Kratsch, Pilipczuk and Wahlström on parameterized MinCSP to efficiently solve a generalisation of Multicut with disjunctive cut requests.

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 introduce a new, remarkably powerful tool to the toolbox of algebraic FPT algorithms, determinantal sieving. Given a polynomial P (x1,…,xn) over a field 𝔽 of characteristic 2, on a set of variables X = [x1,. ..,xn}, and a linear matroid M = (X, I) over 𝔽 of rank k, in 2k evaluations of P we can sieve for those terms in the monomial expansion of P which are multilinear and whose support is a basis for M. The known tools of multilinear detection and constrained multilinear detection then correspond to the case where M is a uniform matroid and the truncation of a disjoint union of uniform matroids, respectively. More generally, let the odd support of a monomial m be the set of variables which have odd degree in m. Using 2k evaluations of P, we can sieve for those terms m whose odd support spans M. Applying this framework to well-known efficiently computable polynomial families allows us to simplify, generalize and improve on a range of algebraic FPT algorithms, such as:

The representative sets lemma for linear matroids has many powerful surprising applications in parameterized complexity, including improved FPT dynamic programming algorithms (Fomin et al., JACM 2016) and polynomial kernelization and sparsification results for graph separation problems (Kratsch and Wahlström, JACM 2020). However, its application can be sporadic, as it presupposes the existence of a linear matroid encoding a property relevant to the problem at hand. Correspondingly, although its application led to several new kernelizations (e.g., Almost 2-SAT and restricted variants of MuLTIWAY Cut), there are also several problems left open (e.g., the general case of MuLTIWAY Cut).

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.

We study the parameterized complexity of MinCSP for so-called equality languages, i.e., for finite languages over an infinite domain such as ℕ, where the relations are defined via first-order formulas whose only predicate is =. This is an important class of languages that forms the starting point of all study of infinite-domain CSPs under the commonly used approach pioneered by Bodirsky, i.e., languages defined as reducts of finitely bounded homogeneous structures. Moreover, MinCSP over equality languages forms a natural class of optimisation problems in its own right, covering such problems as Edge Multicut, Steiner Multicut and (under singleton expansion) Edge Multiway Cut. We classify MinCSP(Γ) for every finite equality language Γ, under the natural parameter, as either FPT, W[1]-hard but admitting a constant-factor FPT-approximation, or not admitting a constant-factor FPT-approximation unless FPT=W[2]. In particular, we describe an FPT case that slightly generalises Multicut, and show a constant-factor FPT-approximation for Disjunctive Multicut, the generalisation of Multicut where the "cut requests" come as disjunctions over O(1) individual cut requests s_i ≠ t_i. We also consider singleton expansions of equality languages, enriching an equality language with the capability for assignment constraints (x = i) for either a finite or infinitely many constants i, and fully characterize the complexity of the resulting MinCSP.

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.

Checking whether a system of linear equations is consistent is a basic computational problem with ubiquitous applications. When dealing with inconsistent systems, one may seek an assignment that minimizes the number of unsatisfied equations. This problem is NP-hard and UGC-hard to approximate within any constant even for two-variable equations over the two-element field. We study this problem from the point of view of parameterized complexity, with the parameter being the number of unsatisfied equations. We consider equations defined over Euclidean domains—a family of commutative rings that generalize finite and infinite fields including the rationals, the ring of integers and many other structures. We show that if every equation contains at most two variables, the problem is fixed-parameter tractable. This generalizes many eminent graph separation problems such as Bipartization, Multiway Cut and Multicut parameterized by the size of the cutset. To complement this, we show that the problem is W[1]-hard when three or more variables are allowed in an equation, as well as for many commutative rings that are not Euclidean domains. On the technical side, we introduce the notion of important balanced subgraphs, generalizing important separators of Marx [Theor. Comput. Sci. 2006] to the setting of biased graphs. Furthermore, we use recent results on parameterized MinCSP [Kim et al., SODA 2021] to efficiently solve a generalization of Multicut with disjunctive cut requests. * The full version of the paper can be accessed at https://arxiv.org/abs/2208.02732

We introduce and study two natural generalizations of the Connected Vertex Cover (VC) problem: the p-Edge-Connected and p-Vertex-Connected VC problem (where p≥2 is a fixed integer). We obtain an 2O(pk)nO(1)-time algorithm for p-Edge-Connected VC and an 2O(k2)nO(1)-time algorithm for p-Vertex-Connected VC. Thus, like Connected VC, both constrained VC problems are FPT. Furthermore, like Connected VC, neither problem admits a polynomial kernel unless NP ⊆ coNP/poly, which is highly unlikely. We prove however that both problems admit time efficient polynomial sized approximate kernelization schemes. Finally, we describe a 2(p+1)-approximation algorithm for the p-Edge-Connected VC. The proofs for the new VC problems require more sophisticated arguments than for Connected VC. In particular, for the approximation algorithm we use Gomory-Hu trees and for the approximate kernels a result on small-size spanning p-vertex/edge-connected subgraphs of a p-vertex/edge-connected graph by Nishizeki and Poljak (1994) and Nagamochi and Ibaraki (1992).

An instance I of the Stable Matching Problem (SMP) is given by a bipartite graph with a preference list of neighbors for every vertex. A swap in I is the exchange of two consecutive vertices in a preference list. A swap can be viewed as a smallest perturbation of I. Boehmer et al. (2021) designed a polynomial-time algorithm for finding the minimum number of swaps required to turn a given maximal matching into a stable matching. We generalize this result to the many-to-many version of SMP. We do so first by introducing a new representation of SMP as an extended bipartite graph and subsequently by reducing the problem to submodular minimization. It is a natural problem to establish the computational complexity of deciding whether at most k swaps are enough to turn I into an instance where one of the maximum matchings is stable. Using a hardness result of Gupta et al. (2020), we prove that this problem is NP-hard and, moreover, this problem parameterised by k is W[1]-hard. We also obtain a lower bound on the running time for solving the problem using the Exponential Time Hypothesis.

We study the problem Symmetric Directed Multicut from a parameterized complexity perspective. In this problem, the input is a digraph D, a set of cut requests C = {(s₁,t₁),…,(s_l,t_l)} and an integer k, and the task is to find a set X ⊆ V(D) of size at most k such that for every 1 ≤ i ≤ l, X intersects either all (s_i,t_i)-paths or all (t_i,s_i)-paths. Equivalently, every strongly connected component of D-X contains at most one vertex out of s_i and t_i for every i. This problem is previously known from research in approximation algorithms, where it is known to have an O(log k log log k)-approximation. We note that the problem, parameterized by k, directly generalizes multiple interesting FPT problems such as (Undirected) Vertex Multicut and Directed Subset Feedback Vertex Set. We are not able to settle the existence of an FPT algorithm parameterized purely by k, but we give three partial results: An FPT algorithm parameterized by k+l; an FPT-time 2-approximation parameterized by k; and an FPT algorithm parameterized by k for the special case that the cut requests form a clique, Symmetric Directed Multiway Cut. The existence of an FPT algorithm parameterized purely by k remains an intriguing open possibility.

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.

Abstract A directed graph D is semicomplete if for every pair x, y of vertices of D, there is at least one arc between x and y. Thus, a tournament is a semicomplete digraph. In the Directed Component Order Connectivity (DCOC) problem, given a digraph $$D=(V,A)$$ D = ( V , A ) and a pair of natural numbers k and $$\ell $$ ℓ , we are to decide whether there is a subset X of V of size k such that the largest strongly connected component in $$D-X$$ D - X has at most $$\ell $$ ℓ vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem for $$\ell =1.$$ ℓ = 1 . We study the parameterized complexity of DCOC for general and semicomplete digraphs with the following parameters: $$k, \ell ,\ell +k$$ k , ℓ , ℓ + k and $$n-\ell $$ n - ℓ . In particular, we prove that DCOC with parameter k on semicomplete digraphs can be solved in time $$O^*(2^{16k})$$ O ∗ ( 2 16 k ) but not in time $$O^*(2^{o(k)})$$ O ∗ ( 2 o ( k ) ) unless the Exponential Time Hypothesis (ETH) fails. The upper bound $$O^*(2^{16k})$$ O ∗ ( 2 16 k ) implies the upper bound $$O^*(2^{16(n-\ell )})$$ O ∗ ( 2 16 ( n - ℓ ) ) for the parameter $$n-\ell .$$ n - ℓ . We complement the latter by showing that there is no algorithm of time complexity $$O^*(2^{o({n-\ell })})$$ O ∗ ( 2 o ( n - ℓ ) ) unless ETH fails. Finally, we improve (in dependency on $$\ell $$ ℓ ) the upper bound of Göke, Marx and Mnich (2019) for the time complexity of DCOC with parameter $$\ell +k$$ ℓ + k on general digraphs from

We study the Many-Visits Traveling Salesman Problem, where given a number k(v) for each of n cities and pairwise (possibly asymmetric) integer distances, one has to find an optimal tour that visits each city v exactly k(v) times. The currently fastest algorithm is due to Berger, Kozma, Mnich and Vincze [SODA 2019, TALG 2020] and runs in time and space O⁎(5n). They also show a polynomial-space algorithm running in time O(16n+o(n)). In this work, we show three main results: A randomized polynomial-space algorithm running in time O⁎(2nD), where D is the maximum distance between two cities. By using standard methods, this results in a (1+ϵ)-approximation running in time O⁎(2nϵ−1). A tight analysis of Berger et al.'s exponential-space algorithm, resulting in an O⁎(4n) running time bound. A new polynomial-space algorithm, running in time O(7.88n).

We show the existence of an exact mimicking network of k O ( log k ) edges for minimum multicuts over a set of terminals in an undirected graph, where k is the total capacity of the terminals, i.e., the sum of the degrees of the terminal vertices. Furthermore, using the best available approximation algorithm for Small Set Expansion , we show that a mimicking network of k O ( log3 k ) edges can be computed in randomized polynomial time. As a consequence, we show quasipolynomial kernels for several problems, including Edge Multiway Cut , Group Feedback Edge Set for an arbitrary group, and Edge Multicut parameterized by the solution size and the number of cut requests. The result combines the matroid-based irrelevant edge approach used in the kernel for s -Multiway Cut with a recursive decomposition and sparsification of the graph along sparse cuts. This is the first progress on the kernelization of Multiway Cut problems since the kernel for s -Multiway Cut for constant value of s (Kratsch and Wahlström, FOCS 2012).

Let $G$ be a graph and $S, T \subseteq V(G)$ be (possibly overlapping) sets of terminals, $|S|=|T|=k$. We are interested in computing a vertex sparsifier for terminal cuts in $G$, i.e., a graph $H$ on a smallest possible number of vertices, where $S \cup T \subseteq V(H)$ and such that for every $A \subseteq S$ and $B \subseteq T$ the size of a minimum $(A,B)$-vertex cut is the same in $G$ as in $H$. We assume that our graphs are unweighted and that terminals may be part of the min-cut. In previous work, Kratsch and Wahlström (FOCS 2012/JACM 2020) used connections to matroid theory to show that a vertex sparsifier $H$ with $O(k^3)$ vertices can be computed in randomized polynomial time, even for arbitrary digraphs $G$. However, since then, no improvements on the size $O(k^3)$ have been shown. In this paper, we draw inspiration from the renowned Bollobás's Two-Families Theorem in extremal combinatorics and introduce the use of total orderings into Kratsch and Wahlström's methods. This new perspective allows us to construct a sparsifier $H$ of $Θ(k^2)$ vertices for the case that $G$ is a DAG. We also show how to compute $H$ in time near-linear in the size of $G$, improving on the previous $O(n^{ω+1})$. Furthermore, $H$ recovers the closest min-cut in $G$ for every partition $(A,B)$, which was not previously known. Finally, we show that a sparsifier of size $Ω(k^2)$ is required, both for DAGs and for undirected edge cuts.

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.

Golovach, Paulusma, and Song [ Inform. and Comput., 237 (2014), pp. 204--214] asked to determine the parameterized complexity of the following problems parameterized by $k$: 1. Given a graph $G$, a clique modulator $D$ (a clique modulator is a set of vertices, whose removal results in a clique) of size $k$ for $G$, and a list $L(v)$ of colors for every $v\in V(G)$, decide whether $G$ has a proper list coloring. 2. Given a graph $G$, a clique modulator $D$ of size $k$ for $G$, and a pre-coloring $\lambda_P: X \rightarrow Q$ for $X \subseteq V(G),$ decide whether $\lambda_P$ can be extended to a proper coloring of $G$ using only colors from $Q$. For problem 1 we design an ${\mathcal O}^*(2^k)$-time randomized algorithm and for problem 2 we obtain a kernel with at most $3k$ vertices. Banik et al. [in Proceedings of IWOCA 2019, Springer, Berlin, 2019, pp. 61--69] proved the following problem is fixed-parameter tractable and asked whether it admits a polynomial kernel: Given a graph $G$, an integer $k$, and a list $L(v)$ of exactly $n-k$ colors for every $v \in V(G),$ decide whether there is a proper list coloring for $G$. We obtain a kernel with ${\mathcal O}(k^2)$ vertices and colors and a compression to a variation of the problem with ${\mathcal O}(k)$ vertices and ${\mathcal O}(k^2)$ colors.

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.

Abasi et al. (2014) introduced the following two problems. In the r -S imple k -P ath problem, given a digraph G on n vertices and positive integers r , k , decide whether G has an r -simple k -path, which is a walk where every vertex occurs at most r times and the total number of vertex occurrences is k . In the ( r , k )-M onomial D etection problem, given an arithmetic circuit that succinctly encodes some polynomial P on n variables and positive integers k , r , decide whether P has a monomial of total degree k where the degree of each variable is at most r . Abasi et al. obtained randomized algorithms of running time 4 ( k / r )log r ⋅ n O (1) for both problems. Gabizon et al. (2015) designed deterministic 2 O (( k / r )log r ) ⋅ n O (1) -time algorithms for both problems (however, for the ( r , k )-M onomial D etection problem the input circuit is restricted to be non-canceling). Gabizon et al. also studied the following problem. In the P -S et ( r , q )-P acking P roblem , given a universe V , positive integers ( p , q , r ), and a collection H of sets of size P whose elements belong to V , decide whether there exists a subcollection H ′ of H of size q where each element occurs in at most r sets of H ′ . Gabizon et al. obtained a deterministic 2 O (( pq / r )log r ) ⋅ n O (1) -time algorithm for P -S et ( r , q )-P acking . The above results prove that the three problems are single-exponentially fixed-parameter tractable (FPT) parameterized by the product of two parameters, that is, k / r and log r , where k = pq for P -S et ( r , q )-P acking . Abasi et al. and Gabizon et al. asked whether the log r factor in the exponent can be avoided. Bonamy et al. (2017) answered the question for ( r , k )-M onomial D etection by proving that unless the Exponential Time Hypothesis (ETH) fails there is no 2 o (( k / r ) log r ) ⋅ ( n + log k ) O (1) -time algorithm for ( r , k )-M onomial D etection , i.e., ( r , k )-M onomial D etection is unlikely to be single-exponentially FPT when parameterized by k / r alone. The question remains open for r -S imple k -P ath and P -S et ( r , q )-P acking . We consider the question from a wider perspective: are the above problems FPT when parameterized by k / r only, i.e., whether there exists a computable function f such that the problems admit a f ( k / r )( n +log k ) O (1) -time algorithm? Since r can be substantially larger than the input size, the algorithms of Abasi et al. and Gabizon et al. do not even show that any of these three problems is in XP parameterized by k / r alone. We resolve the wider question by (a) obtaining a 2 O (( k / r ) 2 log( k / r )) ⋅ ( n + log k ) O (1) -time algorithm for

Publikacja bezkosztowa

We show the existence of an exact mimicking network of k^O(log k) edges for minimum multicuts over a set of terminals in an undirected graph, where k is the total capacity of the terminals. Furthermore, if Small Set Expansion has an approximation algorithm with a ratio slightly better than Θ(log n), then a mimicking network of quasipolynomial size can be computed in polynomial time. As a consequence of the latter, several problems would have quasipolynomial kernels, including Edge Multiway Cut, Group Feedback Edge Set for an arbitrary group, 0-Extension for integer-weighted metrics, and Edge Multicut parameterized by the solution and the number of cut requests. The result works via a combination of the matroid-based irrelevant edge approach used in the kernel for s-Multiway Cut with a recursive decomposition and sparsification of the graph along sparse cuts. The main technical contribution is a matroid-based marking procedure that we can show will mark all non-irrelevant edges, assuming that the graph is sufficiently densely connected. The only part of the result that is not currently constructive and polynomial-time computable is the detection of such sparse cuts. This is the first progress on the kernelization of Multiway Cut problems since the kernel for s-Multiway Cut for constant value of s (Kratsch and Wahlström, FOCS 2012).

A directed graph D is semicomplete if for every pair x,y of vertices of D, there is at least one arc between x and y. Thus, a tournament is a semicomplete digraph. In the Directed Component Order Connectivity (DCOC) problem, given a digraph D = (V,A) and a pair of natural numbers k and 𝓁, we are to decide whether there is a subset X of V of size k such that the largest strong connectivity component in D-X has at most 𝓁 vertices. Note that DCOC reduces to the Directed Feedback Vertex Set problem for 𝓁 = 1. We study parameterized complexity of DCOC for general and semicomplete digraphs with the following parameters: k, 𝓁, 𝓁+k and n-𝓁. In particular, we prove that DCOC with parameter k on semicomplete digraphs can be solved in time O^*(2^(16k)) but not in time O^*(2^o(k)) unless the Exponential Time Hypothesis (ETH) fails. The upper bound O^*(2^(16k)) implies the upper bound O^*(2^(16(n-𝓁))) for the parameter n-𝓁. We complement the latter by showing that there is no algorithm of time complexity O^*(2^o(n-𝓁)) unless ETH fails. Finally, we improve (in dependency on 𝓁) the upper bound of Göke, Marx and Mnich (2019) for the time complexity of DCOC with parameter 𝓁+k on general digraphs from O^*(2^O(k𝓁 log (k𝓁))) to O^*(2^O(klog (k𝓁))). Note that Drange, Dregi and van 't Hof (2016) proved that even for the undirected version of DCOC on split graphs there is no algorithm of running time O^*(2^o(klog 𝓁)) unless ETH fails and it is a long-standing problem to decide whether Directed Feedback Vertex Set admits an algorithm of time complexity O^*(2^o(klog k)).

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.

We continue the development of matroid-based techniques for kernelization, initiated by the present authors [47]. We significantly extend the usefulness of matroid theory in kernelization by showing applications of a result on representative sets due to Lovász [51] and Marx [53]. As a first result, we show how representative sets can be used to derive a polynomial kernel for the elusive ALMOST 2- SAT problem (where the task is to remove at most k clauses to make a 2- CNF formula satisfiable), solving a major open problem in kernelization. This result also yields a new O(√log OPT)-approximation for the problem, improving on the O(√log n)-approximation of Agarwal et al. [3] and an implicit O(log OPT)-approximation due to Even et al. [24]. We further apply the representative sets tool to the problem of finding irrelevant vertices in graph cut problems, that is, vertices that can be made undeletable without affecting the answer to the problem. This gives the first significant progress towards a polynomial kernel for the MULTIWAY CUT problem; in particular, we get a kernel of O( k s+1 ) vertices for MULTIWAY CUT instances with at most s terminals. Both these kernelization results have significant spin-off effects, producing the first polynomial kernels for a range of related problems. More generally, the irrelevant vertex results have implications for covering min cuts in graphs. For a directed graph G=(V,E) and sets S, T ⊆ V , let r be the size of a minimum ( S,T )-vertex cut (which may intersect S and T ). We can find a set Z ⊆ V of size O(|S| . |T| . r) that contains a minimum ( A,B )-vertex cut for every A ⊆ S , B ⊆ T . Similarly, for an undirected graph G=(V,E) , a set of terminals X ⊆ V , and a constant s , we can find a set Z ⊆ V of size O(|X| s+1 ) that contains a minimum multiway cut for every partition of X into at most s pairwise disjoint subsets. Both results are polynomial time. We expect this to have further applications; in particular, we get direct, reduction rule-based kernelizations for all problems above, in contrast to the indirect compression-based kernel previously given for ODD CYCLE TRANSVERSAL [47]. All our results are randomized, with failure probabilities that can be made exponentially small in n , due to needing a representation of a matroid to apply the representative sets tool.

Abasi et al. (2014) introduced the following two problems. In the r-Simple k-Path problem, given a digraph G on n vertices and positive integers r, k, decide whether G has an r-simple k-path, which is a walk where every vertex occurs at most r times and the total number of vertex occurrences is k. In the (r, k)-Monomial Detection problem, given an arithmetic circuit that succinctly encodes some polynomial P on n variables and positive integers k, r, decide whether P has a monomial of total degree k where the degree of each variable is at most r. Abasi et al. obtained randomized algorithms of running time 4(k/r)log r ·nO(1) for both problems. Gabizon et al. (2015) designed deterministic 2O((k/r)log r) · nO(1)-time algorithms for both problems (however, for the (r, k)-Monomial Detection problem the input circuit is restricted to be noncanceling). Gabizon et al. also studied the following problem. In the p-Set (r, q)-Packing problem, given a universe V, positive integers p, q, r, and a collection ℋ of sets of size p whose elements belong to V, decide whether there exists a subcollection ℋ' of ℋ of size q where each element occurs in at most r sets of ℋ'. Gabizon et al. obtained a deterministic 2O((pq/r)log r) ·nO(1)-time algorithm for p-Set (r, q)-Packing. The above results prove that the three problems are single-exponentially fixed-parameter tractable (FPT) when parameterized by the product of two parameters, that is, k/r and log r, where k = pq for p-Set (r, q)-Packing. Abasi et al. and Gabizon et al. asked whether the log r factor in the exponent can be avoided. Bonamy et al. (2017) answered the question for (r, k)-Monomial Detection by proving that unless the Exponential Time Hypothesis (ETH) fails there is no 2o((k/r) log r) · (n + log k)O(1)-time algorithm for (r, k)-Monomial Detection, i.e. (r, k)-Monomial Detection is highly unlikely to be single-exponentially FPT when parameterized by k/r alone. The question remains open for r-Simple k-Path and p-Set (r, q)-Packing. We consider the question from a wider perspective: are the above problems FPT when parameterized by k/r only, i.e. whether there exists a computable function f such that the problems admit a f(k/r)(n + log k)O(1)-time algorithm? Since r can be substantially larger than the input size, the algorithms of Abasi et al. and Gabizon zon et al. do not even show that any of these three problems is in XP parameterized by k/r alone. We resolve the wider question by (a) obtaining a 2O((k/r)2 log(k/r)) · (n + log k)O(1)-time algorithm for r-Simple k-Peth on digraphs and a 2O(k/r) ·(n+log k)O(1)-time algorithm for r-Simple k-Path on undirected graphs (i.e., for undirected graphs we answer the original question in affirmative), (b) showing that p-Set (r, q)-Packing is FPT (in contrast, we prove that p-Multiset (r, q)-Packing is W[1]-hard), and (c) proving that (r, k)-Monomial Detrction is para-NP-hard even if only two distinct variables are in polynomial P and the circuit is noncanceling. For the special case of (r, k)-Monomial Detection here k is polynomially bounded by the input size (which is in XP), we show W[1]-hardness. Along the way to solve p-Set (r, q)-Packing, we obtain a polynomial kernel for any fixed p, which resolves a question posed by Gabizon et al. regarding the existence of polynomial kernels for problems with relaxed disjointness constraints. All our algorithms are deterministic.

We study several problems related to graph modification under connectivity constraints from the perspective of parameterized complexity. In particular, we study (a) (Weighted) Biconnectivity Deletion, where we are tasked with deleting k edges while preserving biconnectivity in an undirected graph, and (b) Path-contraction Preserving Strong Connectivity, where we want to maintain strong connectivity of a digraph while path-contracting k arcs. The parameterized tractability of this last problem was posed in Bang-Jensen and Yeo (2008) [1] as an open question and we answer it here in the negative. On the other hand, we show that preserving (weighted) biconnectivity is fixed-parameter tractable (FPT) and the unweighted case even admits a randomized polynomial kernel. Finally, we show that the most general case of the (unweighted) problem where one would like to preserve ρ-vertex connectivity for any ρ is (non-uniformly) FPT parameterized by k and ρ.

We consider the problems ZERO EXTENSION and METRIC LABELLING under the paradigm of parameterized complexity. These are natural, well-studied problems with important applications, but have previously not received much attention from parameterized complexity. Depending on the chosen cost function $μ$, we find that different algorithmic approaches can be applied to design FPT-algorithms: for arbitrary $μ$ we parameterized by the number of edges that cross the cut (not the cost) and show how to solve ZERO EXTENSION in time $O(|D|^{O(k^2)} n^4 \log n)$ using randomized contractions. We improve this running time with respect to both parameter and input size to $O(|D|^{O(k)} m)$ in the case where $μ$ is a metric. We further show that the problem admits a polynomial sparsifier, that is, a kernel of size $O(k^{|D|+1})$ that is independent of the metric $μ$. With the stronger condition that $μ$ is described by the distances of leaves in a tree, we parameterize by a gap parameter $(q - p)$ between the cost of a true solution $q$ and a `discrete relaxation' $p$ and achieve a running time of $O(|D|^{q-p} |T|m + |T|ϕ(n,m))$ where $T$ is the size of the tree over which $μ$ is defined and $ϕ(n,m)$ is the running time of a max-flow computation. We achieve a similar running for the more general METRIC LABELLING, while also allowing $μ$ to be the distance metric between an arbitrary subset of nodes in a tree using tools from the theory of VCSPs. We expect the methods used in the latter result to have further applications.

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.

An out-branching and an in-branching of a digraph D are called k -distinct if each of them has k arcs absent in the other. Bang-Jensen, Saurabh and Simonsen (2016) proved that the problem of deciding whether a strongly connected digraph D has k -distinct out-branching and in-branching is fixed-parameter tractable (FPT) when parameterized by k . They asked whether the problem remains FPT when extended to arbitrary digraphs. Bang-Jensen and Yeo (2008) asked whether the same problem is FPT when the out-branching and in-branching have the same root. By linking the two problems with the problem of whether a digraph has an out-branching with at least k leaves (a leaf is a vertex of out-degree zero), we first solve the problem of Bang-Jensen and Yeo (2008). We then develop a new digraph decomposition and using it prove that the problem of Bang-Jensen et al. (2016) is FPT for all digraphs.

We give a combinatorial condition for the existence of efficient, LP-based FPT algorithms for a broad class of graph-theoretical optimisation problems. Our condition is based on the notion of biased graphs known from ma- troid theory. Specifically, we show that given a biased graph Ψ = (G, B), where B is a class of balanced cycles in G, the problem of finding a set X of at most k vertices in G which intersects every unbalanced cycle in G admits an FPT algorithm using an LP-branching approach, similar to those previously seen for VCSP problems (Wahlström, SODA 2014). Our algorithm has two parts. First we define a local problem, where we are additionally given a root vertex v0 G V and asked only to delete vertices X (excluding v0) so that the connected component of v0 in G - X contains no unbalanced cycle. We show that this local problem admits a persistent, half-integral LP-relaxation with a polynomial-time solvable separation oracle, and can therefore be solved in FPT time via LP-branching, assuming only oracle membership queries for the class of balanced cycles in G. We then show that solutions to this local problem can be used to tile the graph, producing an optimal solution to the original, global problem as well. This framework captures many of the problems previously solved via the VCSP approach to LP-branching, as well as new generalisations, such as Group Feedback Vertex Set for infinite groups (e.g., for graphs whose edges are labelled by matrices). A major advantage compared to previous work is that it is immediate to check the applicability of the result for a given problem, whereas testing applicability of the VCSP approach for a specific VCSP, requires determining the existence of an embedding language with certain algebraically defined properties, which is not known to be decidable in general.

Two well-studied closure operators for relations are based on existentially quantified conjunctive formulas, primitive positive (p.p.) definitions, and primitive positive formulas without existential quantification, quantifier-free primitive positive definitions (q.f.p.p.) definitions. Sets of relations closed under p.p. definitions are known as co-clones and sets of relations closed under q.f.p.p. definitions as weak partial co-clones. The latter do however have limited expressivity, and the corresponding lattice of strong partial clones is of uncountably infinite cardinality even for the Boolean domain. Hence, it is reasonable to consider the expressiveness of p.p. definitions where only a small number of existentially quantified variables are allowed. In this article, we consider p.p. definitions allowing only polynomially many existentially quantified variables, and say that a co-clone closed under such definitions is polynomially closed, and otherwise superpolynomially closed. We investigate properties of polynomially closed co-clones and prove that if the corresponding clone contains a k-ary near-unanimity operation for k≥3⁠, then the co-clone is polynomially closed, and if the clone does not contain a k-edge operation for any k≥2⁠, then the co-clone is superpolynomially closed. For the Boolean domain we strengthen these results and prove a complete dichotomy theorem separating polynomially closed co-clones from superpolynomially closed co-clones. Using these results, we then proceed to investigate properties of strong partial clones corresponding to superpolynomially closed co-clones. We prove that if Γ is a finite set of relations over an arbitrary finite domain such that the clone corresponding to Γ is essentially unary, then the strong partial clone corresponding to Γ is of infinite order and cannot be generated by a finite set of partial functions.

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

A recent trend in parameterized algorithms is the application of polytope tools to fixed-parameter tractable (FPT) algorithms [e.g., Cygan et al., FOCS 2011, 52nd Annual Symposium on Foundations of Computer Science, IEEE, 2011, pp. 150--159; Narayanaswamy et al., STACS 2012, Symposium on Theoretical Aspects of Computer Science, 2012, pp. 338--349]. Although this approach has yielded significant speedups for a range of important problems, it requires the underlying polytope to have very restrictive properties, including half-integrality and Nemhauser--Trotter-style persistence properties. To date, these properties are essentially known to hold only for two classes of polytopes, covering the cases of Vertex Cover [Nemhauser and Trotter, Math. Program., 8 (1975), pp. 232--248] and Node Multiway Cut [Garg et al., J. Alg., 50 (2004), pp. 49--61]. Taking a slightly different approach, we view half-integrality as a discrete relaxation of a problem, e.g., a relaxation of the search space from $\{0,1\}^V$ to $\{0,1/2,1\}^V$ such that the new problem admits a polynomial-time exact solution. Using tools from constraint satisfaction problems [in particular Thapper and Živný, FOCS 2012, 53rd Annual Symposium on Foundations of Computer Science, IEEE, 2012, pp. 669--678] to study the existence of such relaxations, we are able to provide a much broader class of half-integral polytopes with the required properties. Our results unify and significantly extend the previously known cases, and yield a range of new and improved FPT algorithms, including an $O^*(|\Sigma|^{2k})$-time algorithm for node-deletion Unique Label Cover and an $O^*(4^k)$-time algorithm for Group Feedback Vertex Set where the group is given by oracle access. The latter result also implies the first single-exponential time FPT algorithm for Subset Feedback Vertex Set, answering an open question of Cygan et al. [Algorithmica, 74 (2016), pp. 630--642]. Additionally, we propose a network-flow-based approach to solve several cases of the relaxation problem. This gives the first linear-time FPT algorithm to edge-deletion Unique Label Cover.

In the mixed Chinese postman problem (MCPP), given a weighted mixed graph $G$ (it may have both edges and arcs), our aim is to find a closed walk of minimum weight traversing each edge and arc at least once. The MCPP parameterized by the number of edges in $G$ or the number of arcs in $G$ is fixed-parameter tractable as proved by van Bevern et al. in 2014 and Gutin, Jones, and Sheng in 2014, respectively. Solving an open question of van Bevern et al., we show that somewhat unexpectedly the MCPP parameterized by the (undirected) treewidth of $G$ is W[1]-hard. In fact, we prove that even the unweighted MCPP parameterized by the pathwidth of $G$ is W[1]-hard. On the positive side, we show that MCPP parameterized by treedepth is fixed-parameter tractable (even with arbitrary integer weights). We are unaware of any widely studied graph parameters between pathwidth and treedepth and so our results provide a close characterization of the complexity of MCPP.

The field of exact exponential time algorithms for non-deterministic polynomial-time hard problems has thrived since the mid-2000s. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, non-trivial exponential time algorithms have been found for a myriad of problems, including G raph C oloring , H amiltonian P ath , D ominating S et , and 3-CNF-S at . In some instances, improving these algorithms further seems to be out of reach. The CNF-S at problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O (2 n ), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-S at that run in time o (2 n ), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every ϵ < 1, there is a (large) integer k such that k -CNF-S at cannot be computed in time 2 ϵ n . In this article, we show that, for every ϵ < 1, the problems H itting S et , S et S plitting , and NAE-S at cannot be computed in time O (2 ϵ n ) unless SETH fails. Here n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for S et C over and prove that, under this assumption, the fastest known algorithms for S teiner T ree , C onnected V ertex C over , S et P artitioning , and the pseudo-polynomial time algorithm for S ubset S um cannot be significantly improved. Finally, we justify our assumption about the hardness of S et C over by showing that the parity of the number of solutions to S et C over cannot be computed in time O (2 ϵ n ) for any ϵ < 1 unless SETH fails.

A workflow specification defines a set of steps, a set of users, and an access control policy. The policy determines which steps a user is authorized to perform and imposes constraints on which sets of users can perform which sets of steps. The workflow satisfiability problem (WSP) is the problem of determining whether there exists an assignment of users to workflow steps that satisfies the policy. Given the computational hardness of WSP and its importance in the context of workflow management systems, it is important to develop algorithms that are as efficient as possible to solve WSP. In this article, we study the fixed-parameter tractability of WSP in the presence of class-independent constraints, which enable us to (1) model security requirements based on the groups to which users belong and (2) generalize the notion of a user-independent constraint. Class-independent constraints are defined in terms of equivalence relations over the set of users. We consider sets of nested equivalence relations because this enables us to model security requirements in hierarchical organizations. We prove that WSP is fixed-parameter tractable (FPT) for class-independent constraints defined over nested equivalence relations and develop an FPT algorithm to solve WSP instances incorporating such constraints. We perform experiments to evaluate the performance of our algorithm and compare it with that of SAT4J, an off-the-shelf pseudo-Boolean SAT solver. The results of these experiments demonstrate that our algorithm significantly outperforms SAT4J for many instances of WSP.

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.

A recent trend in parameterized algorithms is the application of polytope tools (specifically, LP-branching) to FPT algorithms (e.g., Cygan et al., 2011; Narayanaswamy et al., 2012). Though the list of work in this direction is short, the results are already interesting, yielding significant speedups for a range of important problems. However, the existing approaches require the underlying polytope to have very restrictive properties, including half-integrality and Nemhauser-Trotter-style persistence properties. To date, these properties are essentially known to hold only for two classes of polytopes, covering the cases of Vertex Cover (Nemhauser and Trotter, 1975) and Node Multiway Cut (Garg et al., 1994). Taking a slightly different approach, we view half-integrality as a discrete relaxation of a problem, e.g., a relaxation of the search space from {0,1}V to {0,½,1}V such that the new problem admits a polynomial-time exact solution. Using tools from CSP (in particular Thapper and Živný, 2012) to study the existence of such relaxations, we are able to provide a much broader class of half-integral polytopes with the required properties. Our results unify and significantly extend the previously known cases. In addition to the new insight into problems with half-integral relaxations, our results yield a range of new and improved FPT algorithms, including an O*(|Σ|2k)-time algorithm for node-deletion Unique Label Cover with label set Σ (improving the previous bound of due to Chitnis et al., 2012) and an O*(4k)-time algorithm for Group Feedback Vertex Set, including the setting where the group is only given by oracle access (improving on the previous bound of O*(2O(klogk)) due to Cygan et al., 2012). The latter bound is optimal under the Exponential Time Hypothesis. The latter result also implies the first single-exponential time FPT algorithm for Subset Feedback Vertex Set, answering an open question of Cygan et al. (2012). Interestingly, despite the half-integrality, our result do not imply any approximation results (as may be expected, given the Unique Games-hardness of the covered problems).

The Odd Cycle Transversal problem (OCT) asks whether a given undirected graph can be made bipartite by deleting at most k of its vertices. In a breakthrough result, Reed, Smith, and Vetta (Operations Research Letters, 2004) gave a O (4 k kmn) time algorithm for it; this also implies that instances of the problem can be reduced to a so-called problem kernel of size O (4 k ). Since then, the existence of a polynomial kernel for OCT (i.e., a kernelization with size bounded polynomially in k ) has turned into one of the main open questions in the study of kernelization, open even for the special case of planar input graphs. This work provides the first (randomized) polynomial kernelization for OCT. We introduce a novel kernelization approach based on matroid theory, where we encode all relevant information about a problem instance into a matroid with a representation of size polynomial in k . This represents the first application of matroid theory to kernelization.

We give an algebraic, determinant-based algorithm for the K-Cycle problem, i.e., the problem of finding a cycle through a set of specified elements. Our approach gives a simple FPT algorithm for the problem, matching the O^*(2^|K|) running time of the algorithm of Björklund et al. (SODA, 2012). Furthermore, our approach is open for treatment by classical algebraic tools (e.g., Gaussian elimination), and we show that it leads to a polynomial compression of the problem, i.e., a polynomial-time reduction of the K-Cycle problem into an algebraic problem with coding size O(|K|^3). This is surprising, as several related problems (e.g., k-Cycle and the Disjoint Paths problem) are known not to admit such a reduction unless the polynomial hierarchy collapses. Furthermore, despite the result, we are not aware of any witness for the K-Cycle problem of size polynomial in |K|+ log n, which seems (for now) to separate the notions of polynomial compression and polynomial kernelization (as a polynomial kernelization for a problem in NP necessarily implies a small witness).

The field of exact exponential time algorithms for NP-hard problems has thrived over the last decade. While exhaustive search remains asymptotically the fastest known algorithm for some basic problems, difficult and non-trivial exponential time algorithms have been found for a myriad of problems, including GRAPH COLORING, HAMILTONIAN PATH, DOMINATING SET and 3-CNF-SAT. In some instances, improving these algorithms further seems to be out of reach. The CNF-SAT problem is the canonical example of a problem for which the trivial exhaustive search algorithm runs in time O(2n), where n is the number of variables in the input formula. While there exist non-trivial algorithms for CNF-SAT that run in time o(2n), no algorithm was able to improve the growth rate 2 to a smaller constant, and hence it is natural to conjecture that 2 is the optimal growth rate. The strong exponential time hypothesis (SETH) by Impagliazzo and Paturi [JCSS 2001] goes a little bit further and asserts that, for every ϵϵn. In this paper, we show that, for every ϵϵn) unless SETH fails. Here n is the number of elements or variables in the input. For these problems, we actually get an equivalence to SETH in a certain sense. We conjecture that SETH implies a similar statement for SET COVER, and prove that, under this assumption, the fastest known algorithms for STEINTER TREE, CONNECTED VERTEX COVER, SET PARTITIONING, and the pseudo-polynomial time algorithm for SUBSET SUM cannot be significantly improved. Finally, we justify our assumption about the hardness of SET COVER by showing that the parity of the number of set covers.

The existence of a polynomial kernel for Odd Cycle Transversal was a notorious open problem in parameterized complexity. Recently, this was settled by the present authors (Kratsch and Wahlstrom, SODA 2012), with a randomized polynomial kernel for the problem, using matroid theory to encode How questions over a set of terminals in size polynomial in the number of terminals (rather than the total graph size, which may be superpolynomially larger). In the current work we further establish the usefulness of matroid theory to kernelization by showing applications of a result on representative sets due to Lovasz (Combinatorial Surveys 1977) and Marx (TCS 2009). We show how representative sets can be used to give a polynomial kernel for the elusive Almost 2-sat problem (where the task is to remove at most k clauses to make a 2-CNF formula satisfiable), solving a major open problem in kernelization. We further apply the representative sets tool to the problem of finding irrelevant vertices in graph cut problems, that is, vertices which can be made undeletable without affecting the status of the problem. This gives the first significant progress towards a polynomial kernel for the Multiway Cut problem; in particular, we get a polynomial kernel for Multiway Cut instances with a bounded number of terminals. Both these kernelization results have significant spin-off effects, producing the first polynomial kernels for a range of related problems. More generally, the irrelevant vertex results have implications for covering min-cuts in graphs. In particular, given a directed graph and a set of terminals, we can find a set of size polynomial in the number of terminals (a cut-covering set) which contains a minimum vertex cut for every choice of sources and sinks from the terminal set. Similarly, given an undirected graph and a set of terminals, we can find a set of vertices, of size polynomial in the number of terminals, which contains a minimum multiway cut for every partition of the terminals into a bounded number of sets. Both results are polynomial time. We expect this to have further applications; in particular, we get direct, reduction rule-based kernelizations for all problems above, in contrast to the indirect compression-based kernel previously given for Odd Cycle Transversal. All our results are randomized, with failure probabilities which can be made exponentially small in the size of the input, due to needing a representation of a matroid to apply the representative sets tool.

In the Odd Cycle Transversal (OCT) problem we are given a graph G on n vertices and an integer k, the objective is to determine whether there exists a vertex set O in G of size at most k such that G - O is bipartite. Reed, Smith and Vetta [Oper. Res. Lett., 2004] gave an algorithm for OCT with running time 3^kn^{O(1)}. Assuming the exponential time hypothesis of Impagliazzo, Paturi and Zane, the running time can not be improved to 2^{o(k)}n^{O(1)}. We show that OCT admits a randomized algorithm running in O(n^{O(1)} + 2^{O(sqrt{k} log k)}n) time when the input graph is planar. As a byproduct we also obtain a linear time algorithm for OCT on planar graphs with running time O(n^O(1) + 2O( sqrt(k) log k) n) time. This improves over an algorithm of Fiorini et al. [Disc. Appl. Math., 2008].

The Odd Cycle Transversal problem (OCT) asks whether a given graph can be made bipartite by deleting at most k of its vertices. In a breakthrough result Reed, Smith, and Vetta (Operations Research Letters, 2004) gave a O(4k kmn) time algorithm for it, the first algorithm with polynomial runtime of uniform degree for every fixed k. It is known that this implies a polynomial-time compression algorithm that turns OCT instances into equivalent instances of size at most O(4k), a so-called kernelization. Since then the existence of a polynomial kernel for OCT, i.e., a kernelization with size bounded polynomially in k, has turned into one of the main open questions in the study of kernelization. Despite the impressive progress in the area, including the recent development of lower bound techniques (Bodlaender et al., ICALP 2008; Fortnow and Santhanam, STOC 2008) and meta-results on kernelizations for graph problems on planar and other sparse graph classes (Bodlaender et al., FOCS 2009; Fomin et al., SODA 2010), the existence of a polynomial kernel for OCT has remained open, even when the input is restricted to be planar. This work provides the first (randomized) polynomial kernelization for OCT. We introduce a novel kernelization approach based on matroid theory, where we encode all relevant information about a problem instance into a matroid with a representation of size polynomial in k. For OCT, the matroid is built to allow us to simulate the computation of the iterative compression step of the algorithm of Reed, Smith, and Vetta, applied (for only one round) to an approximate odd cycle transversal which it is aiming to shrink to size k. The process is randomized with one-sided error exponentially small in k, where the result can contain false positives but no false negatives, and the size guarantee is cubic in the size of the approximate solution. Combined with an -approximation (Agarwal et al., STOC 2005), we get a reduction of the instance to size O(k4.5), implying a randomized polynomial kernelization. Interestingly, the known lower bound techniques can be seen to exclude randomized kernels that produce no false negatives, as in fact they exclude even co-nondeterministic kernels (Dell and van Melkebeek, STOC 2010). Therefore, our result also implies that deterministic kernels for OCT cannot be excluded by the known machinery.

We analyze the two existing algorithms to generate dependent randomized roundings for the bipartite edge weight rounding problem together with several newly proposed variants of these algorithms. For both the edge-based approach of Gandhi, Khuller, Parthasarathy, Srinivasan (FOCS 2002) and the bit-wise approach of Doerr (STACS 2006) we give a simple derandomization (guaranteeing the same rounding errors as the randomized versions achieve with positive probability). An experimental investigation on different types of random instances show that, contrary to the randomized rounding problem with disjoint cardinality constraints, the bit-wise approach is faster than the edge-based one, while the latter still achieves the best rounding errors. We propose a hybrid approach that, in terms of running time, combines advantages of the two previous approaches; in terms of rounding errors it seems a fair compromise. In all cases, the derandomized versions yield much better rounding errors than the randomized ones. We also test how the algorithms compare when used to solve different broadcast scheduling problems (as suggested by Gandhi et al.). Since this needs more random decisions than just in the rounding process, we need to partially re-prove previous results and simplify the corresponding algorithms to finally derive a derandomized version. Again, the derandomized versions give significantly better approximations than the randomized versions. We tested the algorithms on data taken from the Wikipedia access log. For the maximum throughput version of the problem, the derandomized algorithms compute solutions that are very close to the optimum of the linear relaxation. For the minimum average delay version, Gandhi et al. gave a (2, 1)-bicriteria algorithm, i.e., an algorithm which produces a 2-speed schedule with an average delay which on expectation is no worse than that of the 1-speed optimum. For this problem variant, while the performance guarantee of the algorithms certainly holds, we find that a simple greedy heuristic generally produces superior solutions.

We regard the problem of generating randomized roundings with a single cardinality constraint. This is motivated by recent results of Srinivasan (FOCS 2001), Gandhi et al. (FOCS 2002, J. ACM 2006) and the first author (STACS 2005, STACS 2006). Our work results in (a) an improved version of the bitwise derandomization given by the first author, (b) the first derandomization of Srinivasan's tree-based randomized approach, together with a proof of its correctness, and (c) an experimental comparison of the resulting algorithms. Our experiments show that adding a single cardinality constraint typically reduces the rounding errors and not seriously increases the running times. In general, our derandomization of the tree-based approach is superior to the derandomized bitwise one, while the two randomized versions produce very similar rounding errors. When implementing the derandomized tree-based approach, however, the choice of the tree is important.