Search

For a finite collection of graphs F , the F -M-Deletion (resp. F -TM-Deletion) problem consists in, given a graph G and an integer k , decide whether there exists S ⊆ V (G) with | S | ≤ k such that G ∖ S does not contain any of the graphs in F as a minor (resp. topological minor). We are interested in the parameterized complexity of both problems when the parameter is the treewidth of G , denoted by tw , and specifically in the cases where F contains a single connected planar graph H. We present algorithms running in time 2 O (tw) ⋅ n O (1) , called single-exponential , when H is either P 3 , P 4 , C 4 , the paw , the chair , and the banner for both { H } -M-Deletion and { H } -TM-Deletion , and when H = K 1 , i , with i ≥ 1 , for { H } -TM-Deletion. Some of these algorithms use the rank-based approach introduced by Bodlaender et al. (2015) [7]. This is the second of a series of articles on this topic, and the results given here together with other ones allow us, in particular, to provide a tight dichotomy on the complexity of { H } -M-Deletion in terms of H. [ABSTRACT FROM AUTHOR]

In the Red–Blue Dominating Set problem, we are given a bipartite graph G = ( V B ∪ V R , E ) and an integer k , and asked whether G has a subset D ⊆ V B of at most k “blue” vertices such that each “red” vertex from V R is adjacent to a vertex in D . We provide the first explicit linear kernel for this problem on planar graphs, of size at most 43 k . [ABSTRACT FROM AUTHOR]

For some years it was believed that for “connectivity” problems such as Hamiltonian Cycle , algorithms running in time 2 O ( tw ) ⋅ n O ( 1 ) – called single-exponential – existed only on planar and other topologically constrained graph classes, where tw stands for the treewidth of the n -vertex input graph. This was recently disproved by Cygan et al. [ 3 , FOCS 2011], Bodlaender et al. [ 1 , ICALP 2013], and Fomin et al. [ 11 , SODA 2014], who provided single-exponential algorithms on general graphs for most connectivity problems that were known to be solvable in single-exponential time on topologically constrained graphs. In this article we further investigate the role of planarity in connectivity problems parameterized by treewidth, and convey that several problems can indeed be distinguished according to their behavior on planar graphs. Known results from the literature imply that there exist problems, like Cycle Packing , that cannot be solved in time 2 o ( tw log ⁡ tw ) ⋅ n O ( 1 ) on general graphs but that can be solved in time 2 O ( tw ) ⋅ n O ( 1 ) when restricted to planar graphs. Our main contribution is to show that there exist natural problems that can be solved in time 2 O ( tw log ⁡ tw ) ⋅ n O ( 1 ) on general graphs but that cannot be solved in time 2 o ( tw log ⁡ tw ) ⋅ n O ( 1 ) even when restricted to planar graphs. Furthermore, we prove that Planar Cycle Packing and Planar Disjoint Paths cannot be solved in time 2 o ( tw ) ⋅ n O ( 1 ) . The mentioned negative results hold unless the ETH fails. We feel that our results constitute a first step in a subject that can be further exploited. [ABSTRACT FROM AUTHOR]

The input of the Maximum Colored Cut problem consists of a graph G = (V , E) with an edge-coloring c : E → { 1 , 2 , 3 , ... , p } and a positive integer k , and the question is whether G has a nontrivial edge cut using at least k colors. The Colorful Cut problem has the same input but asks for a nontrivial edge cut using all p colors. Unlike what happens for the classical Maximum Cut problem, we prove that both problems are NP -complete even on complete, planar, or bounded treewidth graphs. Furthermore, we prove that Colorful Cut is NP -complete even when each color class induces a clique of size at most three, but is trivially solvable when each color induces an edge. On the positive side, we prove that Maximum Colored Cut is fixed-parameter tractable when parameterized by either k or p , by constructing a cubic kernel in both cases. [ABSTRACT FROM AUTHOR]

A target set selection model is a graph G with a threshold function τ : V (G) → N upper-bounded by the vertex degree. For a given model, a set S 0 ⊆ V (G) is a target set if V (G) can be partitioned into non-empty subsets S 0 , S 1 , ... , S t such that, for all i ∈ { 1 , ... , t } , S i contains exactly every vertex v outside S 0 ∪ ⋯ ∪ S i − 1 having at least τ (v) neighbors in S 0 ∪ ⋯ ∪ S i − 1 . We say that t is the activation time t τ (S 0) of the target set S 0. The problem of, given such a model, finding a target set of minimum size has been extensively studied in the literature. In this article, we investigate its variant, which we call TSS-time , in which the goal is to find a target set S 0 that maximizes t τ (S 0). That is, given a graph G , a threshold function τ in G , and an integer k , the objective of the TSS-time problem is to decide whether G contains a target set S 0 such that t τ (S 0) ≥ k. Let τ ⋆ = max v ∈ V (G) τ (v). Our main result is the following dichotomy about the complexity of TSS-time when G belongs to a minor-closed graph class C : if C has bounded local treewidth, the problem is FPT parameterized by k and τ ⋆ ; otherwise, it is NP -complete even for fixed k = 4 and τ ⋆ = 2. We also prove that, with τ ∗ = 2 , the problem is NP -hard in bipartite graphs for fixed k = 5 , and from previous results we observe that TSS-time is NP -hard in planar graphs and W [1]-hard parameterized by treewidth. Finally, we present a linear-time algorithm to find a target set S 0 in a given tree maximizing t τ (S 0). [ABSTRACT FROM AUTHOR]

During the last years, several algorithmic meta-theorems have appeared (Bodlaender et al. [FOCS 2009], Fomin et al. [SODA 2010], Kim et al. [ICALP 2013]) guaranteeing the existence of linear kernels on sparse graphs for problems satisfying some generic conditions. The drawback of such general results is that it is usually not clear how to derive from them constructive kernels with reasonably low explicit constants. To fill this gap, we recently presented [STACS 2014] a framework to obtain explicit linear kernels for some families of problems whose solutions can be certified by a subset of vertices. In this article we enhance our framework to deal with packing problems, that is, problems whose solutions can be certified by collections of subgraphs of the input graph satisfying certain properties. F -Packing is a typical example: for a family F of connected graphs that we assume to contain at least one planar graph, the task is to decide whether a graph G contains k vertex-disjoint subgraphs such that each of them contains a graph in F as a minor. We provide explicit linear kernels on sparse graphs for the following two orthogonal generalizations of F -Packing: for an integer ℓ ⩾ 1 , one aims at finding either minor-models that are pairwise at distance at least ℓ in G (ℓ - F -Packing), or such that each vertex in G belongs to at most ℓ minors-models (F -Packing with ℓ -Membership). Finally, we also provide linear kernels for the versions of these problems where one wants to pack subgraphs instead of minors. [ABSTRACT FROM AUTHOR]

In an edge-colored graph, the cost incurred at a vertex on a path when two incident edges with different colors are traversed is called reload or changeover cost. The Minimum Changeover Cost Arborescence ( MinCCA ) problem consists in finding an arborescence with a given root vertex such that the total changeover cost of the internal vertices is minimized. It has been recently proved by Gözüpek et al. (2016) that the MinCCA problem when parameterized by the treewidth and the maximum degree of the input graph is in FPT . In this article we present the following hardness results for MinCCA : • the problem is W [1]-hard when parameterized by the vertex cover number of the input graph, even on graphs of degeneracy at most 3. In particular, it is W [1]-hard parameterized by the treewidth of the input graph, which answers the main open problem in the work of Gözüpek et al. (2016); • it is W [1]-hard on multigraphs parameterized by the tree-cutwidth of the input multigraph; and • it remains NP -hard on planar graphs even when restricted to instances with at most 6 colors and 0/1 symmetric costs, or when restricted to instances with at most 8 colors, maximum degree bounded by 4, and 0/1 symmetric costs. [ABSTRACT FROM AUTHOR]

Minor Containment is a fundamental problem in Algorithmic Graph Theory used as a subroutine in numerous graph algorithms. A model of a graph H in a graph G is a set of disjoint connected subgraphs of G indexed by the vertices of H, such that if { u, v} is an edge of H, then there is an edge of G between components C and C. A graph H is a minor of G if G contains a model of H as a subgraph. We give an algorithm that, given a planar n-vertex graph G and an h-vertex graph H, either finds in time $\mathcal{O}(2^{\mathcal{O}(h)} \cdot n +n^{2}\cdot\log n)$ a model of H in G, or correctly concludes that G does not contain H as a minor. Our algorithm is the first single-exponential algorithm for this problem and improves all previous minor testing algorithms in planar graphs. Our technique is based on a novel approach called partially embedded dynamic programming. [ABSTRACT FROM AUTHOR]