Non-monotone target sets for threshold values restricted to 0, 1, and the vertex degree
share
We consider a non-monotone activation process (X_t)_t∈{ 0,1,2,…} on a graph G, where X_0⊆ V(G), X_t={ u∈ V(G):|N_G(u)∩ X_t-1|≥τ(u)} for every positive integer t, and τ:V(G)→ℤ is a threshold function. The set X_0 is a so-called non-monotone target set for (G,τ) if there is some t_0 such that X_t=V(G) for every t≥ t_0. 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)∈{ 0,1,d_G(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 graphs of maximum degree 4 but is efficiently solvable for graphs of bounded treewidth.
READ FULL TEXT