Introduction
In social choice theory, information diffusion models typically examine how a single piece of information propagates through a single network. However, real-world social dynamics are characterized by individuals participating in multiple, overlapping social circles—such as professional networks, family groups, and hobbyist communities—each with distinct connection structures. This paper investigates the computational complexity of controlling information spread when secrets must be contained across two different network layers simultaneously.
Problem Formulation: The DLDD Problem
The authors introduce the Delete Agent LSR Destructive-Destructive (DLDD) problem. In this model, an agent aims to prevent two distinct secrets from reaching specific target groups in two separate networks defined over the same set of vertices (agents).
- Network Model: Two directed graphs $G_1 = (V, E_1)$ and $G_2 = (V, E_2)$ share the same set of agents $V$.
- Starting Rule: The "Liberal Starting Rule" (LSR) is employed, where any agent with a self-loop initially possesses the secret and propagates it along directed edges.
- Objective: Identify a set of at most $k$ agents to "delete" (silence) such that Secret A does not reach target set $T_1$ in $G_1$, and Secret B does not reach target set $T_2$ in $G_2$.
Complexity Results
The core contribution of this work is establishing the theoretical bounds of the DLDD problem. The researchers prove that finding the optimal set of $k$ agents to silence is both NP-complete and W[1]-hard.
The hardness is demonstrated through a reduction from 3-SAT. As shown in Figure 1, the construction involves two network layers: $\varphi_1$ manages variable assignments and auxiliary constraints, while $\varphi_2$ ensures that clause requirements are met. The interdependence between these layers makes the problem significantly more difficult than controlling spread in a single network. The W[1]-hardness result implies that the problem is likely not Fixed-Parameter Tractable (FPT) with respect to the number of deleted agents $k$; even for small values of $k$, the computation time grows exponentially with the total number of agents.
Algorithmic Bounds and Variants
Beyond DLDD, the authors explored the Delete Agent LSR Constructive-Destructive (DLCD) variant, where the goal is to spread one secret while suppressing another. Both variants remain NP-complete even under restrictive conditions, such as short propagation durations or small target sets. While FPT algorithms remain elusive for the general case, the authors developed XP algorithms, which provide a polynomial-time solution when the parameter $k$ is treated as a fixed constant, providing a theoretical upper bound on the problem's difficulty.
Conclusion and Future Work
This research highlights the "two-network trap": while managing information in a single social circle may be computationally feasible, satisfying cross-network constraints introduces extreme complexity. Future research directions include investigating the "Consent Starting Rule" (CSR), where agents only adopt a secret after hearing it from multiple sources, and exploring probabilistic "gossip" models to better reflect the uncertainty of real-world social interactions.
Summary updated