Algorithms and Complexity of Influence Maximization on Directed Acyclic Graphs
It clarifies the computational complexity boundaries of influence maximization for network scientists and algorithm designers, showing that DAGs are still hard but tree-like structures are tractable.
The paper proves that influence maximization is APX-hard on DAGs under the LT model, but becomes tractable on arborescences, with exact polynomial-time algorithms for out-arborescences and an FPTAS for in-arborescences under the IC model.
This paper investigates the influence maximization problem under the Independent Cascade(IC) and Linear Threshold (LT) models. While this problem is known to be APX-hard on general graphs, we explore its computational limits by focusing on Directed Acyclic Graphs (DAGs) and more restricted tree structures. Our primary result demonstrates that influence maximization remains APX-hard on DAGs under the LT model, suggesting that the absence of cycles is insufficient to achieve a polynomial-time approximation scheme (PTAS). In contrast, we show that the problem becomes tractable when the topology is further restricted to out-arborescences and in-arborescences. Specifically, for out-arborescences, we show that the IC model and the LT model are equivalent, and we develop exact polynomial-time algorithms based on dynamic programming that leverage the unique path properties of these structures. For in-arborescences, it is known that the problem is polynomial-time solvable under the LT model, and it is NP-hard under the IC model. We complement these results by presenting a fully polynomial-time approximation scheme (FPTAS) for the IC model.