Search

In a reconfiguration version of a decision problem Q the input is an instance of Q and two feasible solutions S and T. The objective is to determine whether there exists a step-by-step transformation between S and T such that all intermediate steps also constitute feasible solutions. In this work, we study the parameterized complexity of the Connected Dominating Set Reconfiguration problem (CDS-R). It was shown in previous work that the Dominating Set Reconfiguration problem (DS-R) parameterized by k, the maximum allowed size of a dominating set in a reconfiguration sequence, is fixed-parameter tractable on all graphs that exclude a biclique K d , d as a subgraph, for some constant d ≥ 1 . We show that the additional connectivity constraint makes the problem much harder, namely, that CDS-R is W[1]-hard parameterized by k + ℓ , the maximum allowed size of a dominating set plus the length of the reconfiguration sequence, already on 5-degenerate graphs. On the positive side, we show that CDS-R parameterized by k is fixed-parameter tractable, and in fact admits a polynomial kernel on planar graphs. [ABSTRACT FROM AUTHOR]

The Cycle Packing problem asks whether a given undirected graph G = (V;E) con- tains k vertex-disjoint cycles. Since the publication of the classic Erd}os{Posa theorem in 1965, this problem received significant attention in the fields of graph theory and algorithm design. In particu- lar, this problem is one of the first problems studied in the framework of parameterized complexity. The nonuniform fixed-parameter tractability of Cycle Packing follows from the Robertson{Seymour theorem, a fact already observed by Fellows and Langston in the 1980s. In 1994, Bodlaender showed that Cycle Packing can be solved in time 2O(k2) jV j using exponential space. In the case a solu- tion exists, Bodlaender's algorithm also outputs a solution (in the same time). It has later become common knowledge that Cycle Packing admits a 2O(k log2 k) jV j-time (deterministic) algorithm using exponential space, which is a consequence of the Erd}os{Posa theorem. Nowadays, the design of this algorithm is given as an exercise in textbooks on parameterized complexity. Yet, no algorithm that runs in time 2o(k log2 k) jV jO(1), beating the bound 2O(k log2 k) jV jO(1), has been found. In light of this, it seems natural to ask whether the 2O(k log2 k) jV jO(1) bound is essentially optimal. In this paper, we answer this question negatively by developing a 2 O(k log2 k log log k) jV j-time (deterministic) algorithm for Cycle Packing. In the case a solution exists, our algorithm also outputs a solution (in the same time). Moreover, apart from beating the bound 2O(k log2 k) jV jO(1), our algorithm runs in time linear in jV j, and its space complexity is polynomial in the input size. [ABSTRACT FROM AUTHOR]

A vertex-subset graph problem Q defines which subsets of the vertices of an input graph are feasible solutions. A reconfiguration variant of a vertex-subset problem asks, given two feasible solutions of size k , whether it is possible to transform one into the other by a sequence of vertex additions/deletions such that each intermediate set remains a feasible solution of size bounded by k . We study reconfiguration variants of two classical vertex-subset problems, namely Independent Set and Dominating Set . We denote the former by Image 1 and the latter by Image 2 . Both Image 1 and Image 2 are PSPACE -complete on graphs of bounded bandwidth and W[1] -hard parameterized by k on general graphs. We show that Image 1 is fixed-parameter tractable parameterized by k when the input graph is of bounded degeneracy or nowhere dense. For Image 2 , we show the problem fixed-parameter tractable parameterized by k when the input graph does not contain large bicliques. [ABSTRACT FROM AUTHOR]

In the Vertex Cover Reconfiguration (VCR) problem, given a graph G, positive integers k and ι two vertex covers S and T of G of size at most k, we determine whether S can be transformed into T by a sequence of at mostι vertex additions or removals such that every operation results in a vertex cover of size at most k. Motivated by results establishing the W[1]-hardness of VCR when parameterized by ι we delineate the complexity of the problem restricted to various graph classes. In particular, we show that VCR remains W[1]-hard on bipartite graphs, is NP-hard, but fixed-parameter tractable on (regular) graphs of bounded degree and more generally on nowhere dense graphs and is solvable in polynomial time on trees and (with some additional restrictions) on cactus graphs. [ABSTRACT FROM AUTHOR]

Given a Boolean formula and a satisfying assignment, a flip is an operation that changes the value of a variable in the assignment so that the resulting assignment remains satisfying. We study the problem of computing the shortest sequence of flips (if one exists) that transforms a given satisfying assignment s to another satisfying assignment t of an input Boolean formula. Earlier work characterized the complexity of deciding the existence of a sequence of flips between two given satisfying assignments using Schaefer's framework for classification of Boolean formulas. We build on it to provide a trichotomy for the complexity of finding the shortest sequence of flips and show that it is either in P, NP-complete, or PSPACE-complete. Our result adds to the growing set of complexity results known for shortest reconfiguration sequence problems by providing an example where the shortest sequence can be found in polynomial time even though the sequence flips variables that have the same value in both s and t. This is in contrast to most reconfiguration problems studied so far, where polynomial-time algorithms for computing the shortest path were known only for cases where the path modified no more than the symmetric difference of s and t. Our proof uses Birkhoff's representation theorem on a set system that we show to be a distributive lattice. The technique provides insights and can perhaps be used for other reconfiguration problems as well. [ABSTRACT FROM AUTHOR]

Given a graph G and two independent sets I s and I t of size k , the Independent Set Reconfiguration problem asks whether there exists a sequence of independent sets that transforms I s to I t such that each independent set is obtained from the previous one using a so-called reconfiguration step. Viewing each independent set as a collection of k tokens placed on the vertices of a graph G , the two most studied reconfiguration steps are token jumping and token sliding. Over a series of papers, it was shown that the Token Jumping problem is fixed-parameter tractable (for parameter k) when restricted to sparse graph classes, such as planar, bounded treewidth, and nowhere dense graphs. As for the Token Sliding problem, almost nothing is known. We remedy this situation by showing that Token Sliding is fixed-parameter tractable on graphs of bounded degree, planar graphs, and chordal graphs of bounded clique number. [ABSTRACT FROM AUTHOR]

In the Token Sliding problem we are given a graph G and two independent sets I s and I t in G of size k ≥ 1 . The goal is to decide whether there exists a sequence ⟨ I 1 , I 2 , ... , I ℓ ⟩ of independent sets such that for all j ∈ { 1 , ... , ℓ - 1 } the set I j is an independent set of size k, I 1 = I s , I ℓ = I t and I j ▵ I j + 1 = { u , v } ∈ E (G) . Intuitively, we view each independent set as a collection of tokens placed on the vertices of the graph. Then, the problem asks whether there exists a sequence of independent sets that transforms I s into I t where at each step we are allowed to slide one token from a vertex to a neighboring vertex. In this paper, we focus on the parameterized complexity of Token Sliding parameterized by k. As shown by Bartier et al. (Algorithmica 83(9):2914–2951, 2021. https://doi.org/10.1007/s00453-021-00848-1), the problem is W[1]-hard on graphs of girth four or less, and the authors posed the question of whether there exists a constant p ≥ 5 such that the problem becomes fixed-parameter tractable on graphs of girth at least p. We answer their question positively and prove that the problem is indeed fixed-parameter tractable on graphs of girth five or more, which establishes a full classification of the tractability of Token Sliding parameterized by the number of tokens based on the girth of the input graph. [ABSTRACT FROM AUTHOR]

We prove that if (min ⁡ , +) - Convolution can be solved in O (τ (n)) time, then Bisection on treewidth t graphs can be solved in time O (8 t t O (1) log ⁡ n ⋅ τ (n)) , assuming a decomposition of width t as input. Plugging in the O (n 2) time algorithm for (min ⁡ , +) - Convolution yields a O (8 t t O (1) n 2 log ⁡ n) time algorithm for Bisection. This improves over the (dependence on n of the) O (2 t n 3) time algorithm of Jansen et al. [SICOMP 2005] at the cost of a worse dependence on t. "Conversely", we show that if Bisection can be solved in time O (β (n)) on edge weighted trees, then so can (min ⁡ , +) - Convolution. Thus, obtaining a sub-quadratic algorithm for Bisection on trees is extremely challenging, and could even be impossible. On the other hand, for unweighted graphs of treewidth t , by making use of the algorithm for Bounded Difference (min ⁡ , +) - Convolution of Chan and Lewenstein [STOC 2015], we obtain a sub-quadratic algorithm for Bisection with running time O (8 t t O (1) n 1.864 log ⁡ n). [ABSTRACT FROM AUTHOR]

For a graph G , a set D ⊆ V (G) is called a [ 1 , j ] -dominating set if every vertex in V (G) ∖ D has at least one and at most j neighbors in D. A set D ⊆ V (G) is called a [ 1 , j ] -total dominating set if every vertex in V (G) has at least one and at most j neighbors in D. In the [ 1 , j ] -(Total) Dominating Set problem we are given a graph G and a positive integer k. The objective is to test whether there exists a [ 1 , j ] -(total) dominating set of size at most k. The [ 1 , j ] -Dominating Set problem is known to be NP-complete, even for restricted classes of graphs such as chordal and planar graphs, but polynomial-time solvable on split graphs. The [ 1 , 2 ] -Total Dominating Set problem is known to be NP-complete, even for bipartite graphs. As both problems generalize the Dominating Set problem, both are W[1]-hard when parameterized by solution size. In this work, we study the aforementioned problems on various graph classes from the perspective of parameterized complexity and prove the following results: • [ 1 , j ] -Dominating Set parameterized by solution size is W[1]-hard on d -degenerate graphs for d = j + 1. • [ 1 , j ] -Dominating Set parameterized by solution size is FPT on nowhere dense graphs. • The known algorithm for [ 1 , j ] -Dominating Set on split graphs is optimal under the Strong Exponential Time Hypothesis (SETH). • Assuming SETH, we provide a lower bound for the running time of any algorithm solving the [ 1 , 2 ] -Total Dominating Set problem parameterized by pathwidth. • Finally, we study another variant of Dominating Set , called Restrained Dominating Set , that asks if there is a dominating set D of G of size at most k such that no vertex outside of D has all of its neighbors in D. We prove this variant is W[1]-hard even on 3-degenerate graphs. [ABSTRACT FROM AUTHOR]

For \alpha > 1, an \alpha -approximate (bi)kernel is a polynomial-time algorithm that takes as input an instance (I, k) of a problem \scrQ and outputs an instance (I\prime, k\prime) (of a problem \scrQ \prime) of size bounded by a function of k such that, for every c \geq 1, a c-approximate solution for the new instance can be turned into a (c \cdot \alpha)-approximate solution of the original instance in polynomial time. This framework of lossy kernelization was recently introduced by Lokshtanov and co-authors. We study Connected Dominating Set (and its distance-r variant) parameterized by solution size on sparse graph classes like biclique-free graphs, classes of bounded expansion, and nowhere dense classes. We prove that for every \alpha > 1, Connected Dominating Set admits a polynomial-size \alpha -approximate (bi)kernel on all the aforementioned classes. Our results are in sharp contrast to the kernelization complexity of Connected Dominating Set, which is known to not admit a polynomial kernel even on 2-degenerate graphs and graphs of bounded expansion, unless NP \subseteq coNP/poly. We complement our results by the following conditional lower bound. We show that if a class \scrC is somewhere dense and closed under taking subgraphs, then for some value of r \in N there cannot exist an \alpha -approximate bi-kernel for the (Connected) Distance-r Dominating Set problem on \scrC for any \alpha > 1 (assuming FPT \not = W[1]). [ABSTRACT FROM AUTHOR]

Suppose that we are given two dominating sets D s and D t of a graph G whose cardinalities are at most a given threshold k . Then, we are asked whether there exists a sequence of dominating sets of G between D s and D t such that each dominating set in the sequence is of cardinality at most k and can be obtained from the previous one by either adding or deleting exactly one vertex. This decision problem is known to be PSPACE-complete in general. In this paper, we study the complexity of this problem from the viewpoint of graph classes. We first prove that the problem remains PSPACE-complete even for planar graphs, bounded bandwidth graphs, split graphs, and bipartite graphs. We then give a general scheme to construct linear-time algorithms and show that the problem can be solved in linear time for cographs, forests, and interval graphs. Furthermore, for these tractable cases, we can obtain a desired sequence if it exists such that the number of additions and deletions is bounded by O ( n ) , where n is the number of vertices in the input graph. [ABSTRACT FROM AUTHOR]

Supercomputers are equipped with an increasingly large number of cores to use computational power as a way of solving problems that are otherwise intractable. Unfortunately, getting serial algorithms to run in parallel to take advantage of these computational resources remains a challenge for several application domains. Many parallel algorithms can scale to only hundreds of cores. The limiting factors of such algorithms are usually communication overhead and poor load balancing. Solving NP-hard graph problems to optimality using exact algorithms is an example of an area in which there has so far been limited success in obtaining large scale parallelism. Many of these algorithms use recursive backtracking as their core solution paradigm. In this paper, we propose a lightweight, easy-to-use, scalable approach for transforming almost any recursive backtracking algorithm into a parallel one. Our approach incurs minimal communication overhead and guarantees a load-balancing strategy that is implicit, i.e., does not require any problem-specific knowledge. The key idea behind our approach is the use of efficient traversal operations on an indexed search tree that is oblivious to the problem being solved. We test our approach with parallel implementations of algorithms for the well-known Vertex Cover and Dominating Set problems. On sufficiently hard instances, experimental results show nearly linear speedups for thousands of cores, reducing running times from days to just a few minutes. [ABSTRACT FROM AUTHOR]

In the Token Jumping problem we are given a graph G = (V , E) and two independent sets S and T of G, each of size k ≥ 1 . The goal is to determine whether there exists a sequence of k-sized independent sets in G, ⟨ S 0 , S 1 , ... , S ℓ ⟩ , such that for every i, | S i | = k , S i is an independent set, S = S 0 , S ℓ = T , and | S i Δ S i + 1 | = 2 . In other words, if we view each independent set as a collection of tokens placed on a subset of the vertices of G, then the problem asks for a sequence of independent sets which transforms S to T by individual token jumps which maintain the independence of the sets. This problem is known to be PSPACE-complete on very restricted graph classes, e.g., planar bounded degree graphs and graphs of bounded bandwidth. A closely related problem is the Token Sliding problem, where instead of allowing a token to jump to any vertex of the graph we instead require that a token slides along an edge of the graph. Token Sliding is also known to be PSPACE-complete on the aforementioned graph classes. We investigate the parameterized complexity of both problems on several graph classes, focusing on the effect of excluding certain cycles from the input graph. In particular, we show that both Token Sliding and Token Jumping are fixed-parameter tractable on C 4 -free bipartite graphs when parameterized by k. For Token Jumping, we in fact show that the problem admits a polynomial kernel on { C 3 , C 4 } -free graphs. In the case of Token Sliding, we also show that the problem admits a polynomial kernel on bipartite graphs of bounded degree. We believe both of these results to be of independent interest. We complement these positive results by showing that, for any constant p ≥ 4 , both problems are W[1]-hard on { C 4 , ⋯ , C p } -free graphs and Token Sliding remains W[1]-hard even on bipartite graphs. [ABSTRACT FROM AUTHOR]

A key result in the field of kernelization, a subfield of parameterized complexity, states that the classic Disjoint Cycle Packing problem, i.e., finding k vertex disjoint cycles in a given graph G, admits no polynomial kernel unless NP ⊆ coNP/poly. However, very little is known about this problem beyond the aforementioned kernelization lower bound (within the parameterized complexity framework). In the hope of clarifying the picture and better understanding the types of constraints that separate kernelizable from nonkernelizable variants of Disjoint Cycle Packing, we investigate two relaxations of the problem. The first variant, which we call Almost Disjoint Cycle Packing, introduces a global relaxation parameter t. That is, given a graph G and integers k and t, the goal is to find at least k distinct cycles such that every vertex of G appears in at most t of the cycles. The second variant, Pairwise Disjoint Cycle Packing, introduces a local relaxation parameter, and we seek at least k distinct cycles such that every two cycles intersect in at most t vertices. While the Pairwise Disjoint Cycle Packing problem admits a polynomial kernel for all t ≥ 1, the kernelization complexity of Almost Disjoint Cycle Packing reveals an interesting spectrum of upper and lower bounds. In particular, for t = k/c, where c could be a function of k, we obtain a kernel of size O(2c² k7+c log³ k) whenever c ∈ o(√k). Thus the kernel size varies from being subexponential when c ∈ o(√k), to quasi-polynomial when c ∈ o(logℓ k), ℓ ∈ R+, and polynomial when c ∈ O(1). We complement these results for Almost Disjoint Cycle Packing by showing that the problem does not admit a polynomial kernel whenever t ∈ O(k∈) for any 0≤∈< 1, unless NP 埦 coNP/poly. [ABSTRACT FROM AUTHOR]