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