Algebraic complexity of path problems

NEW

Problem: Mahr’s Remark 5.5 asks whether Theorem 5.4 remains true for all finite cycle-free directed graphs after removing the hypothesis that the semiring $S$ is idempotent. Reconstructed precisely: for every finite acyclic digraph $E$ and every semiring $S$, Mahr’s adapted computation schemes for the path function should attain the lower bounds $t(E)$ multiplications and $t^*(E)$ additions. The context supports this reconstruction because the remark says this would let one drop the assumption “$S$ idempotent” from Theorem 5.4.

Result: The statement is false.

Take the acyclic digraph with vertices $0,1,2,3,4,5$ and edges

Work over the free non-idempotent semiring $\mathbb N\langle E\rangle$, so distinct paths are distinct monomials and duplicate paths cannot disappear.

The relevant path sets include

Mahr’s multiplication lower-bound contributions are

so $t(E)=11$. His addition bound gives one contribution for each of

hence $t^*(E)=5$.

Suppose an adapted scheme attained $(11,5)$. Since the five outputs above already require the five allowed additions, no further addition gate can produce another two-path intermediate.

For $P_{05}$, the one allowed addition must split $P_{05}$ into two multiplication blocks. The path $015$ can only occur in a block split at vertex $1$, while $045$ can only occur in a block split at vertex $4$. Thus $0125$ must lie in the split-$1$ block and $0345$ in the split-$4$ block; only $012345$ is ambiguous.

If $012345$ lies in the split-$1$ block, then the split-$4$ block is

so the intermediate $\{04,034\}$ is needed. But $\{04,034\}$ cannot be a single adapted product, since the direct edge path $04$ and the path $034$ have no common nontrivial split vertex. Hence it requires an extra addition.

If $012345$ lies in the split-$4$ block, then the split-$1$ block is

so the intermediate $\{15,125\}$ is needed. Again this cannot be a single adapted product, because the direct path $15$ and the path $125$ have no common nontrivial split vertex, so it also requires an extra addition.

Both cases contradict the availability of only five additions. Therefore the idempotence hypothesis in Mahr’s Theorem 5.4 cannot be dropped for all cycle-free graphs.

Citation: Bernd Mahr, “Algebraic complexity of path problems,” RAIRO Informatique Théorique / Theoretical Informatics 16(3), 263–292, 1982, Theorem 5.4 and Remark 5.5. The counterexample above is the resolution given here.