Non-monotone target sets for threshold values restricted to 0, 1, and the vertex degree

DOI10.46298/DMTCS.6844MaRDI QIDQ6045404zbMATH OpenOpenAlexFDO

Authors Julien Baste, Stefan Ehard, Dieter Rautenbach

Publication date 30 May 2023

Published in Discrete Mathematics & Theoretical Computer Science (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2007.03959

zbMATH Keywords

non-monotone activation processtarget set

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Graph theory (05C99) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Programming involving graphs or networks (90C35)

Abstract: We consider a non-monotone activation process $(X_t{)}_{tin0,1,2,ldots}$ on a graph $G$, where $X_{0}subseteqV(G)$, $X_t=uinV(G):|N_G(u)cap{X}_{t-1}|geqau(u)$ for every positive integer $t$, and $au:V(G)omathbbZ$ is a threshold function. The set $X_0$ is a so-called non-monotone target set for $(G,au)$ if there is some $t_0$ such that $X_t=V(G)$ for every $tgeq{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 $au$ satisfying $au(u)in0,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 planar graphs of maximum degree $3$ but is efficiently solvable for graphs of bounded treewidth.

Recommendations

• Target set selection with maximum activation time
• Treewidth governs the complexity of target set selection
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Solving target set selection with bounded thresholds faster than \(2^n\)
• Domination and convexity problems in the target set selection model

Cites work

• A c^k n 5-approximation algorithm for treewidth
• Combinatorial model and bounds for target set selection
• Dynamic monopolies for degree proportional thresholds in connected graphs of girth at least five and trees
• Dynamic monopolies for interval graphs with bounded thresholds
• Generalized degeneracy, dynamic monopolies and maximum degenerate subgraphs
• scientific article; zbMATH DE number 6474901 (Why is no real title available?)
• scientific article; zbMATH DE number 3639144 (Why is no real title available?)
• Irreversible \(k\)-threshold processes: Graph-theoretical threshold models of the spread of disease and of opinion
• Irreversible conversion of graphs
• On some tractable and hard instances for partial incentives and target set selection
• On the approximability of influence in social networks
• Reversible iterative graph processes
• Size bounds for dynamic monopolies
• The Complexity of Multiterminal Cuts
• Treewidth governs the complexity of target set selection
• Treewidth. Computations and approximations

Cited in

(1)

• Target set selection problem for honeycomb networks

This page was built for publication: Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6045404)