Julien Baste ; Stefan Ehard ; Dieter Rautenbach - Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree

dmtcs:6844 - Discrete Mathematics & Theoretical Computer Science, May 13, 2022, vol. 24, no. 1 - https://doi.org/10.46298/dmtcs.6844
Non-monotone target sets for threshold values restricted to $0$, $1$, and the vertex degree

Authors: Julien Baste ; Stefan Ehard ; Dieter Rautenbach

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


    Volume: vol. 24, no. 1
    Section: Graph Theory
    Published on: May 13, 2022
    Accepted on: April 28, 2022
    Submitted on: October 19, 2020
    Keywords: Mathematics - Combinatorics,Computer Science - Discrete Mathematics

    Share

    Consultation statistics

    This page has been seen 389 times.
    This article's PDF has been downloaded 428 times.