Tight inapproximability of target set reconfiguration
Naoto Ohsaka · Discrete Applied Mathematics · 2026
Given a graph G with a vertex threshold function τ , consider a dynamic process in which any inactive vertex v becomes activated whenever at least τ ( 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 NP -hard to approximate Minmax Target Set Reconfiguration within a factor of 2 − o 1 polylog n , 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 NP -hardness of approximation for the former problem is proven by Chen (SIDMA 2009) and Charikar, Naamad, and Wirth (APPROX/RANDOM 2016).