Let 
be an edge-labeled acyclic digraph with distinguished
source 
and target 
, and let 
be the label of edge 
. The 
-
path polynomial of 
is
 |
where the sum is over all directed graph paths 
from 
to 
and the product is taken in the order in which the edges occur
along 
. It is naturally a polynomial in the free noncommutative
semiring, although commutative specializations are also
useful. After adjoining additive inverses, the same expression lies in a free noncommutative ring.
An 
-
path expression, also called a factoring
of 
, is a formula using addition, multiplication, and the
edge labels that represents 
. Its length is the number
of edge-label occurrences in the formula tree. This measure counts repeated subexpressions
each time they occur and therefore differs from the size of a shared algebraic
branching program or circuit.
Setting the labels of a set 
of edges to 0 makes 
vanish if and only if 
is an 
-
edge cut. Moreover, 
is inclusion-minimal if and only if the polynomial remains
nonzero when the zero substitution is instead made for any proper
subset of 
(Korenblit and Levit 2026).
This polynomial should not be confused with the path polynomial 
, whose coefficient
counts graph paths of length 
.
