Zero Forcing Sets in Temporal Graphs

1 Introduction

• The paper frames corruption as a way to study information movement and asks how many entities must initially hold the information, and how fast it spreads.The introduction situates this question in networks that change through evolving social connections or moving agents.Source: §1 · p. 1
• The paper introduces Zero Forcing on temporal graphs, where edges change between snapshots and corruption is resolved at each time step.The goal is to find a minimum-size initial set that eventually corrupts the whole graph.Source: §1 · p. 2
• Temporal Zero Forcing is NP-hard even when the underlying graph is a star, and remains hard with bounded degree and total time.The paper also reports W[1]-hardness parameterized by the forcing-set size.Source: §1 · p. 2
• For bounded-degree temporal trees and stars with polylogarithmically many time steps, the paper provides polynomial algorithms.The single-time-step case is also shown NP-hard, resolving an open question about 1-step corruption.Source: §1 · p. 2

2 Preliminaries

• The static Zero Forcing Set problem uses the same sole-uncorrupted-neighbor rule iteratively, but temporal corruption follows the snapshots in sequence.The static problem asks for a minimum-size set that eventually corrupts the whole graph.Source: §2 · pp. 3–4
• A temporal graph assigns each edge the times when it appears; each snapshot contains the edges present at that time, and the underlying graph removes this timing information.The lifespan is the last time at which an edge appears.Source: §2 · p. 3
• The paper classifies temporal graphs by properties of their underlying graph, so a temporal clique need not be a clique in every snapshot.The structural property requires each underlying edge to appear at least once.Source: §2 · p. 3
• At each snapshot, a corrupted vertex corrupts its sole uncorrupted neighbor, while any corruption newly enabled must wait for a later snapshot.The process is represented by a corrupting function that ends with every vertex corrupted.Source: §2 · pp. 3–4
• A temporal zero forcing set is an initial set that permits complete corruption, and TZ(G) is the minimum cardinality of such a set.The decision problem asks whether a temporal zero forcing set of size at most k exists.Source: §2 · pp. 3–4

3 Hardness of the Temporal Zero Forcing Set problem

• Temporal Zero Forcing is NP-hard when the underlying graph is a star.A polynomial-time construction from a 3-SAT formula has temporal zero forcing number k + 1 exactly when the formula is satisfiable.Source: §3 · p. 4
• The star reduction represents variables and clauses with vertices and arranges snapshots so a size-k + 1 forcing set corresponds exactly to a satisfying assignment.The proof derives the assignment from selected variable vertices and uses clause-vertex corruption to show each clause is satisfied.Source: §3 · pp. 4, 6, 7
• The star construction has polynomial size, with at most 4k + 2 vertices per snapshot and 4k + 6m + 1 snapshots.The reduction’s central mechanism is that a vertex can become corrupted only when an incident edge appears.Source: §3 · p. 5
• NP-hardness persists with lifespan at most 10, underlying maximum degree 6, and snapshot maximum degree 1.The reduction uses 3-SAT instances in which each variable appears at most four times.Source: §3 · p. 7
• The bounded-parameter reduction merges compatible consecutive snapshots into one matching, using the at-most-four-occurrences restriction to limit the number of snapshots.The proof notes that each snapshot then has maximum degree 1 and the underlying graph has maximum degree 6.Source: §3 · pp. 7–8

4 Temporal Graphs of Lifespan 1

• Temporal Zero Forcing Set is NP-hard even when restricted to lifespan-1 graphs, equivalent to the static setting.The section frames this result as addressing a question about zero forcing completed in one step.Source: §4 · p. 8
• For each variable, its gadget is the union of two cliques; for each clause, three uj,k vertices each connect to cj and every vertex of the corresponding literal clique.The uj,k vertices form a clique of size 3r, and the cj vertices form a clique of size r. These are layers 2 and 3, with literal cliques in layer 1; there are no edges between layers 1 and 3.Source: §4 · pp. 8–9
• For a 3-SAT formula Φ, the constructed graph satisfies Φ iff Z(G) ≤ Z × ℓ + 3r.The equivalence supplies the reduction’s decision threshold.Source: §4 · p. 9
• Under the size bound, every variable gadget must contribute a complete one of its two literal cliques to S; a partial choice costs too many vertices.The proof shows that a gadget without a complete clique requires at least 2Z − 2 vertices, making the total exceed the bound.Source: §4 · pp. 10–11
• Soundness turns either a fully seeded layer 2 or a fully seeded layer 3 into a satisfying assignment; all other configurations exceed the size bound.In the first case, each clause has a true literal witness; in the second, each clause vertex’s unique uncorrupted layer-2 neighbor corresponds to a true literal.Source: §4 · pp. 11–12

• The star case is NP-hard and W[1]-hard parameterized by TZ(G), via a reduction where TZ(G)=k+1 exactly when the input has a multicolored k-clique.Source: §5 · pp. 12–13
• Every size k+1 corrupting set contains c or c′ and exactly one v or v′ from each color class.Source: §5 · p. 14
• The reduction’s snapshots encode selected color-class vertices and pairwise adjacency: y_i,j is forced only through x_uv for the selected endpoints.Source: §5 · pp. 14–15
• When k=n−T on a temporal star, at most one vertex is corrupted per snapshot, and the problem is polynomial-time solvable.Source: §5 · p. 15
• For center-seeded solutions, the polynomial test requires every W_i to be nonempty; when a neighbor corrupts c first, the corresponding sets must be nonempty for all later snapshots.Source: §5 · p. 16
• If T−k is polylogarithmic in |V(G)|, the star case is polynomial-time solvable by enumerating candidate snapshot sets and invoking the exact-case algorithm.Source: §5 · p. 16

6 Bounded-Degree Trees

• The cited result establishes that Temporal Zero Forcing Set is solvable in polynomial time when the underlying graph of the input temporal graph is a bounded-degree tree.Source: §6 · p. 16
• A bottom-up dynamic program roots the tree and stores bounded information per vertex when the maximum degree is bounded.Source: §6 · pp. 16–17
• For each vertex, the table prices guessed local corruption scenarios by the minimum size of a matching partial temporal zero forcing set.Source: §6 · p. 17
• Pruning entries to possible neighboring corruption sources reduces the table size and improves the algorithm’s runtime bound.Source: §6 · p. 18
• Temporal Zero Forcing Set on trees is fixed-parameter tractable by lifespan plus maximum degree.Source: §6 · p. 19

7 Conclusion

• Temporal Zero Forcing Set is NP-hard on stars and even when lifespan and both underlying-graph and snapshot degrees are bounded, while bounded-degree trees are tractable.Source: §7 · p. 19
• The lifespan-1 case is hard in general, answering an open question about minimum static zero forcing sets with propagation time one.Source: §7 · p. 19
• The authors conjecture fixed-parameter tractability by treewidth plus lifespan, noting that the conjecture holds when all snapshots are identical.Source: §7 · p. 19
• The conclusion asks what results arise when multiple corruption rounds are allowed within a single snapshot.Source: §7 · p. 19