pith. sign in

arxiv: 2606.00585 · v1 · pith:QYVFOO4Jnew · submitted 2026-05-30 · 💻 cs.GT

Algorithms and Complexity of Influence Maximization on Directed Acyclic Graphs

Panfeng Liu , Biaoshuai Tao This is my paper

Pith reviewed 2026-06-28 18:20 UTC · model grok-4.3

classification 💻 cs.GT
keywords influence maximizationdirected acyclic graphslinear threshold modelindependent cascade modelAPX-hardnessdynamic programmingarborescences
0
0 comments X

The pith

Influence maximization under the linear threshold model remains APX-hard on directed acyclic graphs.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper studies the difficulty of selecting an initial seed set to maximize spread in networks governed by the independent cascade or linear threshold diffusion rules. It narrows attention to directed acyclic graphs to test whether removing cycles makes the problem easier to approximate. The main result establishes that the linear threshold version stays APX-hard on DAGs, so the lack of cycles does not produce a polynomial-time approximation scheme. When the graph is further restricted to out-arborescences, the two diffusion models become equivalent and admit exact polynomial-time dynamic programming algorithms that exploit the single-path structure. On in-arborescences the linear threshold model is already polynomial-time solvable while the independent cascade model, though NP-hard, possesses a fully polynomial-time approximation scheme.

Core claim

Influence maximization remains APX-hard on DAGs under the LT model, so acyclicity alone is insufficient for a PTAS. On out-arborescences the IC and LT models are equivalent and both admit exact polynomial-time solutions via dynamic programming. On in-arborescences the LT model is polynomial-time solvable while the IC model admits an FPTAS.

What carries the argument

An APX-hardness reduction that embeds a known hard instance into an LT diffusion process on a DAG without creating cycles, together with dynamic programming that computes exact influence along the unique paths of arborescences.

If this is right

  • No PTAS exists for LT influence maximization on DAGs unless P=NP.
  • Exact polynomial-time algorithms exist for both IC and LT on out-arborescences.
  • An FPTAS exists for IC influence maximization on in-arborescences.
  • The IC and LT models coincide exactly on out-arborescences.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The hardness may stem from multiple overlapping paths rather than the mere presence of cycles.
  • Similar dynamic programming techniques could apply to other tree-like or low-treewidth DAGs.
  • The FPTAS for IC on in-arborescences may extend to DAGs with bounded in-degree.

Load-bearing premise

The reduction produces a valid DAG whose maximum influence value and approximation gap are preserved from the original APX-hard problem.

What would settle it

A polynomial-time algorithm that approximates the maximum influence value under the LT model on DAGs to within a factor better than the known APX-hardness threshold would falsify the claim.

Figures

Figures reproduced from arXiv: 2606.00585 by Biaoshuai Tao, Panfeng Liu.

Figure 1
Figure 1. Figure 1: Reduction gadget: Converting an edge (u, v) of the original graph into a gadget for the influence maximization instance. 1 whenever their respective parent node is activated, thereby amplifying the influence differences within the gadget. Finally, this gadget is duplicated three more times (the vertices u and v in the original graph are not duplicated, the remaining part of the gadget has four identical co… view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The paper investigates influence maximization under the Independent Cascade (IC) and Linear Threshold (LT) models, focusing on DAGs and restricted arborescence topologies. It claims APX-hardness for LT on general DAGs (showing acyclicity alone does not yield a PTAS), equivalence of IC and LT with exact DP algorithms on out-arborescences, known poly-time solvability for LT and NP-hardness for IC on in-arborescences, and a new FPTAS for IC on in-arborescences.

Significance. If the hardness reduction is correct, the result clarifies the boundary between approximable and inapproximable cases for influence maximization by showing that DAG structure is insufficient for a PTAS under LT; this narrows the topological conditions needed for efficient approximation. The exact DP algorithms on out-arborescences and the FPTAS on in-arborescences are constructive contributions that exploit path uniqueness and could be useful in applications with tree-like networks.

minor comments (3)
  1. The abstract and introduction should explicitly define out-arborescences versus in-arborescences (including direction of edges) before stating the equivalence and complexity results.
  2. In the DP sections for out-arborescences, include a brief statement confirming that the recurrence runs in polynomial time (e.g., O(n^2) or similar) and state the precise running time.
  3. Add a short remark on whether the FPTAS for IC on in-arborescences is tight or if a PTAS is also possible, to contextualize the result relative to the NP-hardness.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive summary, significance assessment, and recommendation to accept the manuscript. The review accurately captures the main results on APX-hardness of LT on DAGs, equivalence and exact DP on out-arborescences, and the FPTAS for IC on in-arborescences.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes APX-hardness of influence maximization under the LT model on DAGs via an explicit reduction from a known hard problem that preserves acyclicity and the approximation gap; this is an independent constructive argument, not a self-definition or fitted input. Tractability results on out-arborescences and in-arborescences rely on dynamic programming that exploits unique path properties and known equivalences between models, again without reducing to self-referential definitions or self-citation chains. No equations or claims equate a derived quantity to its own inputs by construction, and external citations (e.g., prior poly-time results on in-arborescences) are not load-bearing for the novel DAG hardness claim. The derivation chain is therefore self-contained as standard complexity-theoretic reasoning.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The abstract invokes only standard complexity-theoretic assumptions and graph-theoretic definitions; no free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)
  • standard math Standard assumptions of complexity theory (P ≠ NP, existence of APX-hard problems)
    Implicitly used to establish APX-hardness via reduction.

pith-pipeline@v0.9.1-grok · 5723 in / 1305 out tokens · 23641 ms · 2026-06-28T18:20:56.131040+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 6 canonical work pages

  1. [1]

    In: Web and Internet Economics: 13th International Conference, WINE 2017, Bangalore, India, December 17–20, 2017, Proceedings 13

    Angell, R., Schoenebeck, G.: Don’t be greedy: Leveraging community structure to find high quality seed sets for influence maximization. In: Web and Internet Economics: 13th International Conference, WINE 2017, Bangalore, India, December 17–20, 2017, Proceedings 13. pp. 16–29. Springer (2017)

    2017

  2. [2]

    Journal of Consumer Research14(3), 350–362 (12 1987)

    Brown, J.J., Reingen, P.H.: Social Ties and Word-of-Mouth Referral Behavior*. Journal of Consumer Research14(3), 350–362 (12 1987). https://doi.org/10.1086/209118, https://doi.org/10.1086/209118

    work page doi:10.1086/209118 1987

  3. [3]

    Chen,N.:Ontheapproximabilityofinfluenceinsocialnetworks.SIAMJournalonDiscreteMathematics 23(3), 1400–1415 (2009)

    2009

  4. [4]

    In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining

    Chen, W., Wang, C., Wang, Y.: Scalable influence maximization for prevalent viral marketing in large- scale social networks. In: Proceedings of the 16th ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 1029–1038 (2010)

    2010

  5. [5]

    In: 2010 IEEE international conference on data mining

    Chen, W., Yuan, Y., Zhang, L.: Scalable influence maximization in social networks under the linear threshold model. In: 2010 IEEE international conference on data mining. pp. 88–97. IEEE (2010)

    2010

  6. [6]

    Journal of the ACM (JACM)54(3), 12–es (2007)

    Dinur, I.: The pcp theorem by gap amplification. Journal of the ACM (JACM)54(3), 12–es (2007)

    2007

  7. [7]

    In: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Min- ing

    Domingos, P., Richardson, M.: Mining the network value of customers. In: Proceedings of the Seventh ACM SIGKDD International Conference on Knowledge Discovery and Data Min- ing. p. 57–66. KDD ’01, Association for Computing Machinery, New York, NY, USA (2001). https://doi.org/10.1145/502512.502525, https://doi.org/10.1145/502512.502525

    work page doi:10.1145/502512.502525 2001

  8. [8]

    Feige, U.: A threshold of ln n for approximating set cover. J. ACM45(4), 634–652 (jul 1998). https://doi.org/10.1145/285055.285059, https://doi.org/10.1145/285055.285059

    work page doi:10.1145/285055.285059 1998

  9. [9]

    Theory Comput.11, 105–147 (2015)

    Kempe, D., Kleinberg, J.M., Tardos, É.: Maximizing the spread of influence through a social network. Theory Comput.11, 105–147 (2015)

    2015

  10. [10]

    In: Proceedings of the twenty- fifth annual ACM-SIAM symposium on Discrete algorithms

    Khanna, S., Lucier, B.: Influence maximization in undirected networks. In: Proceedings of the twenty- fifth annual ACM-SIAM symposium on Discrete algorithms. pp. 1482–1496. SIAM (2014)

    2014

  11. [11]

    Proceedings of the International AAAI Conference on Web and Social Media4(1), 90–97 (May 2010)

    Lerman, K., Ghosh, R.: Information contagion: An empirical study of the spread of news on digg and twitter social networks. Proceedings of the International AAAI Conference on Web and Social Media4(1), 90–97 (May 2010). https://doi.org/10.1609/icwsm.v4i1.14021, https://ojs.aaai.org/index.php/ICWSM/article/view/14021

    work page doi:10.1609/icwsm.v4i1.14021 2010

  12. [12]

    Journal of Combinatorial Optimization33, 803–808 (2017)

    Lu, Z., Zhang, Z., Wu, W.: Solution of bharathi–kempe–salek conjecture for influence maximization on arborescence. Journal of Combinatorial Optimization33, 803–808 (2017)

    2017

  13. [13]

    SIAM Journal on Computing39, 2176–2188 (1 2010)

    Mossel, E., Roch, S.: Submodularity of influence in social networks: From local to global. SIAM Journal on Computing39, 2176–2188 (1 2010). https://doi.org/10.1137/080714452

    work page doi:10.1137/080714452 2010

  14. [14]

    Mathematical programming14, 265–294 (1978)

    Nemhauser, G.L., Wolsey, L.A., Fisher, M.L.: An analysis of approximations for maximizing submodular set functions—i. Mathematical programming14, 265–294 (1978)

    1978

  15. [15]

    IEEE Journal on Se- lected Areas in Communications31(6), 1084–1094 (2013)

    Nguyen, H., Zheng, R.: On budgeted influence maximization in social networks. IEEE Journal on Se- lected Areas in Communications31(6), 1084–1094 (2013)

    2013

  16. [16]

    Phys- ical Review E63(6), 066117 (2001)

    Pastor-Satorras, R., Vespignani, A.: Epidemic dynamics and endemic states in complex networks. Phys- ical Review E63(6), 066117 (2001)

    2001

  17. [17]

    In: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining

    Richardson, M., Domingos, P.: Mining knowledge-sharing sites for viral marketing. In: Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining. pp. 61–70 (2002)

    2002

  18. [18]

    Rigobon, R.: Contagion: How to Measure It? In: Preventing Currency Crises in Emerging Markets, pp. 269–334. NBER Chapters, National Bureau of Economic Research, Inc (2002), https://ideas.repec.org/h/nbr/nberch/10638.html

    2002

  19. [19]

    ACM Transactions on Computation Theory (TOCT)11(3), 1–56 (2019)

    Schoenebeck, G., Tao, B.: Beyond worst-case (in) approximability of nonsubmodular influence maxi- mization. ACM Transactions on Computation Theory (TOCT)11(3), 1–56 (2019)

    2019

  20. [20]

    ACM Transactions on Economics and Computation (TEAC)8(4), 1–36 (2020)

    Schoenebeck, G., Tao, B.: Influence maximization on undirected graphs: Toward closing the (1-1/e) gap. ACM Transactions on Economics and Computation (TEAC)8(4), 1–36 (2020)

    2020

  21. [21]

    arXiv preprint arXiv:2002.11679 (2020)

    Schoenebeck, G., Tao, B., Yu, F.Y.: Limitations of greed: Influence maximization in undirected networks re-visited. arXiv preprint arXiv:2002.11679 (2020)

    work page arXiv 2002

  22. [22]

    Information and Computation285, 104919 (2022) Algorithms and Complexity of Influence Maximization on DAGs 15

    Schoenebeck, G., Tao, B., Yu, F.Y.: Think globally, act locally: On the optimal seeding for nonsubmod- ular influence maximization. Information and Computation285, 104919 (2022) Algorithms and Complexity of Influence Maximization on DAGs 15

    2022

  23. [23]

    Journal of Combinatorial Optimization31, 1678–1684 (2016)

    Wang, A., Wu, W., Cui, L.: On bharathi–kempe–salek conjecture for influence maximization on arbores- cence. Journal of Combinatorial Optimization31, 1678–1684 (2016)

    2016