Given an edge-weighted directed graph, how do you sum over all weighted paths between A and B while using the smallest number of multiplications?

enter image description here Is there a name for this problem?

This comes up in automatic differentiation, and people have shown this to be NP-complete for general graphs. That paper however, relies on autodiff notation, is there an analogue from graph theory community?

Is anything known about tractability of this problem for special graph types? Using dynamic programming on path decomposition should scale exponentially in pathwidth.

I was wondering if this problem is still intractable when restricting to interval graphs

  • 1
    $\begingroup$ Such a structure is called an algebraic branching program in algebraic complexity theory. I am not aware of any result how to evaluate them optimally. $\endgroup$ Jan 19, 2022 at 11:37


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.