pith. sign in

arxiv: 2604.13526 · v1 · submitted 2026-04-15 · 💻 cs.DS · cs.SI

Linear-Time Exact Computation of Influence Spread on Bounded-Pathwidth Graphs

Kengo Nakamura , Masaaki Nishino This is my paper

Pith reviewed 2026-05-10 12:30 UTC · model grok-4.3

classification 💻 cs.DS cs.SI
keywords influence spreadindependent cascade modelpathwidthdynamic programmingexact computationuncertain graphsreachabilityinfluence maximization
0
0 comments X

The pith

Exact influence spread can be computed in linear time on graphs of bounded pathwidth by sharing subcomputations in dynamic programming.

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

The paper develops an algorithm that computes the exact expected number of reachable vertices from given seeds under the independent cascade model. This quantity is evaluated via dynamic programming over a path decomposition of the directed uncertain graph. The improvement reduces runtime from quadratic in the number of edges and vertices to linear in their sum, while the dependence on pathwidth stays the same. A reader would care because the method makes precise influence calculations practical for networks whose structure has small pathwidth, such as trees or series-parallel graphs, without sampling or approximation.

Core claim

The authors identify repetitive identical subproblems that arise when computing reachability probabilities during a path-decomposition traversal of a directed uncertain graph and share those subproblems, yielding an O((m + n) ω_p² · 2^{ω_p²}) algorithm for exact influence spread.

What carries the argument

Dynamic programming on a path decomposition that shares identical subcomputations for directed reachability probabilities in the uncertain graph.

Load-bearing premise

The directed reachability subproblems on the path decomposition contain enough identical computations that can be shared to eliminate the quadratic factor in graph size.

What would settle it

A family of graphs with fixed pathwidth whose reachability DP tables exhibit too few repeated subproblems, leaving the per-bag work quadratic and the overall runtime superlinear.

read the original abstract

Given a network and a set of vertices called seeds to initially inject information, influence spread is the expected number of vertices that eventually receive the information under a certain stochastic model of information propagation. Under the commonly used independent cascade model, influence spread is equivalent to the expected number of vertices reachable from the seeds on a directed uncertain graph, and the exact evaluation of influence spread offers many applications, e.g., influence maximization. Although its evaluation is a \#P-hard task, there is an algorithm that can precisely compute the influence spread in $O(mn\omega_p^2\cdot 2^{\omega_p^2})$ time, where $\omega_p$ is the pathwidth of the graph. We improve this by developing an algorithm that computes the influence spread in $O((m+n)\omega_p^2\cdot 2^{\omega_p^2})$ time. This is achieved by identifying the similarities in the repetitive computations in the existing algorithm and sharing them to reduce computation. Although similar refinements have been considered for the probability computation on undirected uncertain graphs, a greater number of similarities must be leveraged for directed graphs to achieve linear time complexity.

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

1 major / 2 minor

Summary. The manuscript claims an improved algorithm for exactly computing influence spread (expected reachable vertices from seeds) under the independent cascade model on directed uncertain graphs of pathwidth ω_p. It refines a prior O(m n ω_p² · 2^{ω_p²})-time DP on path decompositions to O((m + n) ω_p² · 2^{ω_p²}) time by identifying and sharing repetitive subcomputations on bag interfaces, noting that the directed case requires exploiting more similarities than the undirected setting to eliminate the quadratic factor.

Significance. If the linear-time bound holds, the result would be a meaningful advance for exact #P-hard influence-spread computation on bounded-pathwidth graphs, removing the O(mn) dependence while leaving the 2^{ω_p²} term unchanged. This could support more practical exact methods for influence maximization and diffusion analysis on graphs such as trees, series-parallel graphs, or outerplanar graphs where pathwidth is small. The work follows the standard paradigm of optimizing DP via memoization of shared subproblems, which is a legitimate but technically delicate refinement.

major comments (1)
  1. [The improved DP and running-time analysis] The central running-time claim (abstract and the statement of the improved bound) rests on the assertion that directed reachability subproblems on path-decomposition bags admit O(m + n) distinct configurations rather than O(mn). The manuscript describes the sharing at a high level but does not supply explicit pseudocode, an enumeration of the distinct reachability relations or probability vectors maintained on each bag, or a proof that directionality and uncertain-edge probabilities preserve enough identities to keep the number of unique subproblems linear. Without this accounting it is impossible to confirm that no hidden quadratic factor remains in the DP transitions.
minor comments (2)
  1. The abstract and introduction would benefit from a short concrete example illustrating one shared subcomputation that is identical across different path-decomposition nodes.
  2. Notation for the uncertain-graph model and the precise definition of the bag interface states could be introduced earlier with a small diagram.

Simulated Author's Rebuttal

1 responses · 0 unresolved

Thank you for the opportunity to respond to the referee's report. We address the major comment on the dynamic programming details and running-time analysis below. We agree that the current description of the subcomputation sharing is high-level and will revise the manuscript to provide the requested explicit details and proof.

read point-by-point responses

  1. Referee: The central running-time claim (abstract and the statement of the improved bound) rests on the assertion that directed reachability subproblems on path-decomposition bags admit O(m + n) distinct configurations rather than O(mn). The manuscript describes the sharing at a high level but does not supply explicit pseudocode, an enumeration of the distinct reachability relations or probability vectors maintained on each bag, or a proof that directionality and uncertain-edge probabilities preserve enough identities to keep the number of unique subproblems linear. Without this accounting it is impossible to confirm that no hidden quadratic factor remains in the DP transitions.

    Authors: We acknowledge that the manuscript presents the identification and sharing of repetitive subcomputations at a high level. In the revised version we will add explicit pseudocode for the improved DP. We will also include an enumeration of the distinct reachability relations and probability vectors maintained on each bag, together with a formal proof that the directed structure and uncertain-edge probabilities allow exactly O(m + n) unique subproblems. The proof proceeds by showing that identical partial reachability configurations can be memoized and reused across bag interfaces after a single linear scan of the path decomposition, exploiting additional identities that arise only in the directed case and thereby eliminating the quadratic factor present in the prior algorithm. revision: yes

Circularity Check

0 steps flagged

No circularity: explicit DP construction with memoization sharing

full rationale

The paper derives its O((m+n)ω_p²·2^{ω_p²}) bound by exhibiting a concrete dynamic-programming procedure on a path decomposition that reuses identical subproblems arising from directed reachability configurations on bag interfaces. The improvement over the prior O(mnω_p²·2^{ω_p²}) bound is obtained by an explicit enumeration and sharing argument whose correctness follows from the standard semantics of the independent-cascade reachability DP; no fitted parameters, self-definitional equations, or load-bearing self-citations appear in the derivation chain. The result is therefore an independent algorithmic statement whose running-time claim is not equivalent to its own inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 0 axioms · 0 invented entities

The algorithm rests on standard dynamic programming over path decompositions of directed graphs and on the correctness of the independent-cascade reachability model; no free parameters, ad-hoc axioms, or new invented entities are introduced in the abstract.

pith-pipeline@v0.9.0 · 5495 in / 1154 out tokens · 34895 ms · 2026-05-10T12:30:37.743630+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

8 extracted references · 8 canonical work pages

  1. [1]

    (Almost-)optimal FPT algorithm and kernel for T-Cycle on planar graphs

    1 Antoine Amarilli, Pierre Bourhis, Louis Jachiet, and Stefan Mengel. A circuit-based approach to efficient enumeration. InProc. of the 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), pages 111:1–111:15, 2017.doi:10.4230/LIPIcs.ICALP. 2017.111. 2 Hans L. Bodlaender. A linear-time algorithm for finding tree-decomposition...

    work page doi:10.4230/lipics.icalp 2017

  2. [2]

    4 Wei Chen, Yajun Wang, and Siyu Yang

    doi:10.1145/1835804.1835934. 4 Wei Chen, Yajun Wang, and Siyu Yang. Efficient influence maximization in social networks. InProc. of the 15th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2009), page 199–208, 2009.doi:10.1145/1557019.1557047. 5 Pedro Domingos and Matt Richardson. Mining the network value of customers. InPr...

    work page doi:10.1145/1835804.1835934 2009

  3. [3]

    7 Amit Goyal, Wei Lu, and Laks V.S

    doi:10.1023/A:1011122126881. 7 Amit Goyal, Wei Lu, and Laks V.S. Lakshmanan. CELF++: optimizing the greedy algorithm for influence maximization in social networks. InProc. of the 20th International Conference Companion on World Wide Web (WWW 2011), pages 47–48, 2011.doi:10.1145/1963192. 1963217. 8 Gary Hardy, Corinne Lucet, and Nikolaos Limnios. K-termina...

    work page doi:10.1023/a:1011122126881 2011

  4. [4]

    Kempe, J

    10 David Kempe, Jon Kleinberg, and Éva Tardos. Maximizing the spread of influence through a social network. InProc. of the 9th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD 2003), pages 137–146, 2003.doi:10.1145/956750.956769. 11 Jure Leskovec, Andreas Krause, Carlos Guestrin, Christos Faloutsos, Jeanne VanBriesen, and Na...

    work page doi:10.1145/956750.956769 2003

  5. [5]

    13 Yuchen Li, Dongxiang Zhang, and Kian-Lee Tan

    doi:10.1109/TKDE.2018.2807843. 13 Yuchen Li, Dongxiang Zhang, and Kian-Lee Tan. Real-time targeted influence maximization for online advertisements.Proc. of the VLDB Endowment, pages 1070–1081, 2015.doi: 10.14778/2794367.2794376. 14 Chen Ling, Junji Jiang, Junxiang Wang, My T. Thai, Renhao Xue, James Song, Meikang Qiu, and Liang Zhao. Deep graph represent...

    work page doi:10.1109/tkde.2018.2807843 2018

  6. [6]

    Exact computation of influence spread by binary decision diagrams

    15 Takanori Maehara, Hirofumi Suzuki, and Masakazu Ishihata. Exact computation of influence spread by binary decision diagrams. InProc. of the 26th International Conference on World Wide Web (WWW 2017), pages 947–956, 2017.doi:10.1145/3038912.3052567. 16 Kengo Nakamura, Takeru Inoue, Masaaki Nishino, and Norihito Yasuda. Efficient network reliability eval...

    work page doi:10.1145/3038912.3052567 2017

  7. [7]

    19 Shashank Sheshar Singh, Divya Srivastva, Madhushi Verma, and Jagendra Singh

    doi:10.1609/aaai.v28i1.8726. 19 Shashank Sheshar Singh, Divya Srivastva, Madhushi Verma, and Jagendra Singh. Influence maximization frameworks, performance, challenges and directions on social network: A theoretical study.Journal of King Saud University - Computer and Information Sciences, 34(9):7570–7603, 2022.doi:10.1016/j.jksuci.2021.08.009. 20 Hirofum...

    work page doi:10.1609/aaai.v28i1.8726 2022

  8. [8]

    doi:10.1145/2348283.2348373

    work page doi:10.1145/2348283.2348373