Target Set Selection parameterized by vertex cover and more

Abstract

Given a simple, undirected graph $G$ with a threshold function $\tau :V(G)\to \mathbb{N}$, the \textsc{Target Set Selection} (TSS) problem is about choosing a minimum cardinality set, say $S\subseteq V(G)$, such that starting a diffusion process with $S$ as its seed set will eventually result in activating all the nodes in $G$. For any non-negative integer $i$, we say a set $T\subseteq V(G)$ is a "degree-$i$ modulator" of $G$ if the degree of any vertex in the graph $G-T$ is at most $i$. Degree-$0$ modulators of a graph are precisely its vertex covers. Consider a graph $G$ on $n$ vertices and $m$ edges. We have the following results on the TSS problem: -> It was shown by Nichterlein et al. [Social Network Analysis and Mining, 2013] that it is possible to compute an optimal-sized target set in $O(2^{(2^t+1)t}\cdot m)$ time, where $t$ denotes the cardinality of a minimum degree-$0$ modulator of $G$. We improve this result by designing an algorithm running in time $2^{O(t\log t)}{n}^{O(1)}$. -> We design a $2^{2^{O(t)}}{n}^{O(1)}$ time algorithm to compute an optimal target set for $G$, where $t$ is the size of a minimum degree-$1$ modulator of $G$.

21 pages