Search

Given two integers ℓ and p as well as ℓ graph classes H1, . . ., Hℓ, the problems GraphPart(H1, . . ., Hℓ, p), VertPart(H1, . . ., Hℓ), and EdgePart(H1, . . ., Hℓ) ask, given graph G as input, whether V (G), V (G), E(G) respectively can be partitioned into ℓ sets S1, . . ., Sℓ such that, for each i between 1 and ℓ, G[Si] ∈ Hi, G[Si] ∈ Hi, (V (G), Si) ∈ Hi respectively. Moreover in GraphPart(H1, . . ., Hℓ, p), we request that the number of edges with endpoints in different sets of the partition is bounded by p. We show that if there exist dynamic programming treedecomposition-based algorithms for recognizing the graph classes Hi, for each i, then we can constructively create a dynamic programming tree-decomposition-based algorithms for GraphPart(H1, . . ., Hℓ, p), VertPart(H1, . . ., Hℓ), and EdgePart(H1, . . ., Hℓ). We apply this approach to known problems. For well-studied problems, like VERTEX COVER and GRAPH q-COLORING, we obtain running times that are comparable to those of the best known problemspecific algorithms. For an exotic problem from bioinformatics, called DISPLAYGRAPH, this approach improves the known algorithm parameterized by treewidth. [ABSTRACT FROM AUTHOR]

We consider a non-monotone activation process (Xt)t2{0,1,2,...} on a graph G, where X0 = V (G), Xt = {u 2 V (G): |NG(u) \ Xt-1| = = (u)} for every positive integer t, and =: V (G) ! Z is a threshold function. The set X0 is a so-called non-monotone target set for (G, ι) if there is some t0 such that Xt = V (G) for every t = t0. Ben-Zwi, Hermelin, Lokshtanov, and Newman [Discrete Optimization 8 (2011) 87-96] asked whether a target set of minimum order can be determined efficiently if G is a tree. We answer their question in the affirmative for threshold functions ι satisfying ι (u) 2 {0, 1, dG(u)} for every vertex u. For such restricted threshold functions, we give a characterization of target sets that allows to show that the minimum target set problem remains NP-hard for planar graphs of maximum degree 3 but is efficiently solvable for graphs of bounded treewidth. [ABSTRACT FROM AUTHOR]