Finding Nontrivial Minimum Fixed Points in Discrete Dynamical Systems
Abstract:
Discrete dynamical systems are often used to model the propagation of contagions on networks. Fixed points of such dynamical systems represent configurations for which the dynamics converge. In the dissemination of undesirable contagions (e.g., rumors and misinformation), convergence to fixed points with a small number of affected vertices is a desirable goal. Nevertheless, for some social contagions widely adopted in communities, it is often unrealistic to expect contagions to be completely absent in the population. Motivated by such considerations, we study the problem of finding a fixed point of a system where the number of affected vertices is both (i) nonzero and is (ii) minimized. We refer to the problem as the Nontrivial Minimum Fixed Point Existence Problem (NMIN-FPE). Previously work has shown that NMIN-FPE cannot be approximated within the factor n^(1−epsilon) for any constant epsilon > 0 when the local functions are threshold functions. In this work, we aim to explore the computational complexity of the problem under the inverted-threshold update schemes. Specifically, we establish that NMIN-FPE cannot be approximated to any constant factor unless P = NP. Further, we present several special cases where the problem can be solved efficiently. We also propose a simple heuristics that tackles the problem on real-world networks. Overall, we obtain a detailed theoretical analysis of NMIN-FPE and further extend the problem solvability to cope with its hardness.
Committee:
- Anil Vullikanti, Committee Chair, (CS, Biocomplexity/SEAS/UVA)
- Madhav Marathe, Advisor, (CS, Biocomplexity /SEAS/UVA)
- Jundong Li, (CS, ECE/SEAS, SDS/UVA)
- Hongning Wang (CS/SEAS/UVA)