{"ID":2922007,"CreatedAt":"2026-06-02T02:42:49.606572591Z","UpdatedAt":"2026-06-02T07:21:46.982601397Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2606.00585","arxiv_id":"2606.00585","title":"Algorithms and Complexity of Influence Maximization on Directed Acyclic Graphs","abstract":"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.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2606.00585","url_pdf":"https://arxiv.org/pdf/2606.00585v1","authors":"[\"Panfeng Liu\",\"Biaoshuai Tao\"]","published":"2026-05-30T07:26:46Z","proceeding":"cs.GT","tasks":"[\"cs.GT\"]","methods":"[]","has_code":false}