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

Researchers Kengo Nakamura and Masaaki Nishino have published a paper presenting a new algorithm that achieves a linear-time exact computation of influence spread for graphs with bounded pathwidth. The problem involves calculating the expected number of nodes influenced from a set of seed nodes under stochastic propagation models like the Independent Cascade model, which is foundational for tasks like influence maximization in social networks. While exact evaluation is #P-hard, the new method identifies and shares similarities in repetitive computations from prior algorithms, enabling a significant complexity reduction.

The key technical advancement is reducing the time complexity from O(mnω_p²·2^{ω_p²}) to O((m+n)ω_p²·2^{ω_p²}), where 'm' and 'n' are edges and vertices, and ω_p is the graph's pathwidth. This shift from a product (mn) to a sum (m+n) represents a major efficiency gain, making the algorithm linear in the size of the graph for fixed pathwidth. The authors note that achieving this for directed graphs required leveraging a greater number of computational similarities than previous refinements for undirected graphs.

This work, accepted for SWAT 2026, provides a more practical tool for researchers and data scientists needing exact, rather than approximate, influence calculations. It opens the door for more rigorous optimization in applications where precision is critical, such as designing targeted marketing campaigns or analyzing the robustness of communication networks, especially on structured network datasets where pathwidth is bounded.