[Submitted on 23 Feb 2024 (v1), last revised 6 Aug 2026 (this version, v2)]

View PDF

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}{\operatorname{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).

Submission history

From: Naoto Ohsaka [view email]
[v1] Fri, 23 Feb 2024 03:35:36 UTC (21 KB)
[v2] Thu, 6 Aug 2026 07:12:52 UTC (43 KB)

Current browse context:

cs.DS

Bookmark

Bibliographic and Citation Tools

Code, Data and Media Associated with this Article

Demos

Recommenders and Search Tools

arXivLabs: experimental projects with community collaborators

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.