Search

A vertex subset S in a graph G is a dominating set if every vertex not contained in S has a neighbor in S. A dominating set S is a connected dominating set if the subgraph G[S] induced by S is connected. A connected dominating set S is a minimal connected dominating set if no proper subset of S is also a connected dominating set. We prove that there exists a constant \epsilon ∊10-50 such that every graph G on n vertices has at most O(2(1-∊)n) minimal connected dominating sets. For the same ∊ we also give an algorithm with running time 2(1-∊)n· nO(1) to enumerate all minimal connected dominating sets in an input graph G. [ABSTRACT FROM AUTHOR]

We prove the following theorem. Given a planar graph G and an integer k, it is possible in polynomial time to randomly sample a subset A of vertices of G with the following properties: A induces a subgraph of G of treewidth O(√k log k), and for every connected subgraph H of G on at most k vertices, the probability that A covers the whole vertex set of H is at least (2O(√k log² k)⋅nO(1))-1, where n is the number of vertices of G. Together with standard dynamic programming techniques for graphs of bounded treewidth, this result gives a versatile technique for obtaining (randomized) subexponential-time parameterized algorithms for problems on planar graphs, usually with running time bound 2O(√k log² k)nO(1). The technique can be applied to problems expressible as searching for a small, connected pattern with a prescribed property in a large host graph; examples of such problems include Directed k -Path, Weighted k -Path, Vertex Cover Local Search, and Subgraph Isomorphism, among others. Up to this point, it was open whether these problems could be solved in subexponential parameterized time on planar graphs, because they are not amenable to the classic technique of bidimensionality. Furthermore, all our results hold in fact on any class of graphs that exclude a fixed apex graph as a minor, in particular on graphs embeddable in any fixed surface. [ABSTRACT FROM AUTHOR]

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 EDGE EDITING TO CONNECTED f-Degree Graph problem we are given a graph G, an integer fc, and a function f assigning integers to vertices of G. The task is to decide whether there is a connected graph F on the same vertex set as G, such that for every vertex v, its degree in F is f(v), and the number of edges in E(G)ΔE(F), the symmetric difference of E(G) and E(F), is at most k. We show that Edge EDITING TO CONNECTED f-DEGREE GRAPH is fixed- parameter tractable (FPT) by providing an algorithm solving the problem on an n-vertex graph in time2O(k)nO(1). We complement this result by showing that the weighted version of the problem with costs 1 and 0 is W[l]-hard when parameterized by k and the maximum value of f even when the input graph is a tree. Our FPT algorithm is based on a nontrivial combination of color-coding and fast computations of representative families over the direct sum matroid of l-elongation of the co-graphic matroid associated with G and a uniform matroid over the set of nonedges of G. We believe that this combination could be useful in designing parameterized algorithms for other edge editing and connectivity problems. [ABSTRACT FROM AUTHOR]

In the Steiner Tree problem, we are given as input a connected n-vertex graph with edge weights in {1,2,...,W}, and a set of k terminal vertices. Our task is to compute a minimum-weight tree that contains all of the terminals. The main result of the paper is an algorithm solving Steiner Tree in time O(7.97k·n4·logW) and using O(n3·lognW·logk) space. This is the first single-exponential time, polynomial space FPT algorithm for the weighted Steiner Tree problem. Whereas our main result seeks to optimize the polynomial dependency in n for both the running time and space usage, it is possible to trade between polynomial dependence in n and the single-exponential dependence in k to obtain faster running time as a function of k, but at the cost of increased running time and space usage as a function of n. In particular, we show that there exists a polynomial space algorithm for Steiner Tree running in O(6.751knO(1)logW) time. Finally, by pushing such a trade-off between a polynomial in n and an exponential in k dependencies, we show that for any ϵ > 0 there is an n O(f(ϵ))logW space 4(1+ϵ)kn O(f(ϵ))logW time algorithm for Steiner Tree, where f is a computable function depending only on ϵ. [ABSTRACT FROM AUTHOR]