Tight Inapproximability of Target Set Reconfiguration

Abstract

Given a graph $G$ with a vertex threshold function $\tau$, consider a dynamic process in which any inactive vertex $v$ becomes activated whenever at least $\tau (v)$ of its neighbors have been activated. A vertex set $S$ is called a target set if all vertices of $G$ would eventually be activated when initially activating exactly the vertices of $S$. In the Minmax Target Set Reconfiguration problem, for a graph $G$ and a pair of its target sets $X$ and $Y$, we wish to transform $X$ into $Y$ by repeatedly adding or removing a single vertex, using only target sets of $G$, so as to minimize the maximum size of any intermediate target set. We prove that it is $\mathbf{NP}$-hard to approximate Minmax Target Set Reconfiguration within a factor of $2-o\left(\frac{1}{\mathrm{polylog}n}\right)$, where $n$ is the number of vertices. Our result establishes a tight lower bound on approximability of Minmax Target Set Reconfiguration, which admits a simple $2$-factor approximation algorithm. The proof is based on a gap-preserving reduction from Target Set Selection to Minmax Target Set Reconfiguration, where $\mathbf{NP}$-hardness of approximation for the former problem is proven by Chen (SIDMA 2009) and Charikar, Naamad, and Wirth (APPROX/RANDOM 2016).

arXiv comment14 pages, revised following referee comments