Search

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

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

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 2O(k3)n³ log³ 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. [ABSTRACT FROM AUTHOR]

In the Vertex Planarization problem one asks to delete the minimum possible number of vertices from an input graph to obtain a planar graph. The parameterized complexity of this problem, parameterized by the solution size (the number of deleted vertices) has recently attracted significant attention. The state-of-the-art algorithm of Jansen et al. (2014) runs in time 2 O ( k log k ) ⋅ n on an n -vertex graph with a solution of size k . It remains open if one can obtain a single-exponential dependency on k in the running time bound. One of the core technical contributions of the work of Jansen, Lokshtanov, and Saurabh is an algorithm that solves a weighted variant of Vertex Planarization in time 2 O ( w log w ) ⋅ n on graphs of treewidth w . In this short note we prove that the running time of this routine is tight under the Exponential Time Hypothesis, even in unweighted graphs and when parameterizing by treedepth. Consequently, it is unlikely that a potential single-exponential algorithm for Vertex Planarization parameterized by the solution size can be obtained by merely improving upon the aforementioned bounded treewidth subroutine. [ABSTRACT FROM AUTHOR]

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 G1 and G2 are isomorphic. The running time of the algorithm on an n-vertex graph is ...⋅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 ...⋅n5 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 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 G1 and G2 are equal. [ABSTRACT FROM AUTHOR]

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 2O(k² log ∣Σ∣)n4 log n deterministic time (even in the stronger, vertex-deletion variant), where k is the number of unsatisfied edges and ∣Σ∣ 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(√log n) to optimality, which improves over the trivial O(1) upper bound. We prove that the Steiner Cut problem can be solved in 2O(k² log k)n4 log n deterministic time and Õ(2O(k² log k)n²) 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 2O(k² log k)n4 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. [ABSTRACT FROM AUTHOR]

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 O(16k (n+m)) time. In this paper we present an algorithm with running time kO(k2/3) + O(nm(kn + m)), which is the first subexponential parameterized algorithm for PROPER INTERVAL COMPLETION. [ABSTRACT FROM AUTHOR]

The Multicut problem, given a graph G, a set of terminal pairs T = {(si, ti) Ι 1 ≤ i ≤ 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, ti is not reachable from si for each 1 ≤ i ≤ 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. [ABSTRACT FROM AUTHOR]

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 ⊆ 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 2knO(1) instances with the size of S bounded by O(k³), using kernelization techniques such as the 2-expansion lemma, Menger's theorem, and Gallai's theorem. These two facts allow us to give a 2O(k log k)nO(1) time algorithm solving the Subset-FVS problem, proving that it is indeed fixed-parameter tractable. [ABSTRACT FROM AUTHOR]

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