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?
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