Metraipolis › archive › dc_9b362fd67fe0

Zero Forcing Sets in Temporal Graphs — arXiv:2609.29054

Source
arXiv (en)
Original
https://arxiv.org/abs/2609.29054
License (as archived)
CC0-1.0
Archived
2026-10-08T07:29:23.417Z
SHA-256 of the archived text
d4004083caaad4d72f4abbeed65e9aecdf89493ccc5f182f6139c4548a3f119f
Stable URL of this page
https://metraipolis.com/documento/dc_9b362fd67fe0

How to cite

Zero Forcing Sets in Temporal Graphs — arXiv:2609.29054 — arXiv (en), https://arxiv.org/abs/2609.29054 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_9b362fd67fe0 (Metraipolis archive dc_9b362fd67fe0, sha256 d4004083caaad4d72f4abbeed65e9aecdf89493ccc5f182f6139c4548a3f119f)
BibTeX
@misc{dc9b362fd67fe0,
  title = {Zero Forcing Sets in Temporal Graphs — arXiv:2609.29054},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2609.29054},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_9b362fd67fe0; sha256 d4004083caaad4d72f4abbeed65e9aecdf89493ccc5f182f6139c4548a3f119f},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.29054. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

The Zero Forcing (or corruption) of a graph is the problem of finding a minimum-size ``corrupting'' set. It corresponds to a subset of its vertices that can corrupt the whole graph by iterating the following rule: if a corrupted vertex has exactly one neighbor that is not yet corrupted, the neighbor gets corrupted. The iteration of this process comes from the fact that the corruption of a vertex might enable new corruptions (from itself or some of its neighbors). For this reason, one can consider a step of corruption, where all the possible instances of the corruption rule are applied at once. This paper investigates Zero Forcing on temporal graphs, where the topology of the graph evolves throughout the experiment. At each time step (or snapshot) of the graph, a step of corruption is resolved wherever possible. We study the problem of finding a minimum-size corrupting set such that the whole (temporal) graph is corrupted at the end of the experiment. We present a panorama of results, including NP-hardness in some not-so-restrictive scenarios, polynomial algorithms, and a solution to an open question when the whole graph must be corrupted in a single step.

Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-25 in cs.CC).
Categorie arXiv: Discrete Mathematics (cs.DM) ; Computational Complexity (cs.CC).
Pagina del lavoro: https://arxiv.org/abs/2609.29054 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-08T06:44:58.638Z dalla pagina https://arxiv.org/catchup/cs.CC/2026-09-25?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).