[This is a supplementary material to Chapter 5, Section 5.3]
Bellman-Ford-Moore (min,+) branching program for lightest k-walks is optimal
Recall that a tropical $(\min,+)$ branching program $\Phi$ is
a directed acyclic graph
with one zero indegree node $s$ (the source node) and one zero
outdegree node $t$ (the target node). Programs simultaneously computing several functions may have several target nodes. Multiple edges joining the same
pair of nodes are allowed. Every edge is either labeled by one of the variables
$x_1,\ldots,x_n$ (is a switch) or is unlabeled (is a rectifier). The minimization problem solved by $\Phi$ is the minimum, over all $s$-$t$ paths $\pi$ in $\Phi$, of the sum of labels of the edges along the path $\pi$ (see Fig. 1).
Fig. 1: A $(\min,+)$ branching program with four switches and one rectifier (from $u$ to $v$) solving the minimization problem $f(x,y)=\min\{2x, x+y\}$.
As before,
let $K_n$ be the complete undirected graph on $[n]=\{1,\ldots,n\}$.
The length of a walk in $K_n$ is the number of its edges; if an
edge is traversed several times during the walk, then this edge is counted this number of
times. In the lightest $k$-walk problem, given an assignment
of nonnegative weights $x_{i,j}$ to the edges $\{i,j\}$ of $K_n$, the
goal is to compute the minimum weight
\[
x_{1,i_1} + x_{i_1,i_2}+
x_{i_2,i_3}+\cdots + x_{i_{k-2},i_{k-1}}+x_{i_{k-1},n}
\]
of a walk
$(s,i_1,i_2,\ldots,i_{k-1},t)$ of
length $k$ between the vertices $1$ and $n$, where $i_j\neq i_{j+1}$ for all
$j=1,\ldots,k-2$ (variables $x_{i,j}$ correspond to the edges $\{i,j\}$ of $K_n$),
but $\{i_j,i_{j+1}\}=\{i_l,i_{l+1}\}$ for $j\neq l$
is possible, that is, one can walk through the same edge several times.
The lightest $k$-walk problem on $K_n$ can be solved by a $(\min,+)$ branching program with at most $kn^2$ switches using the Bellman-Ford-Moore $(\min,+)$ DP algorithm (Example 1.7(1)).
The BFM $(\min,+)$ branching program:
We have one source node $s=1$, one target node $t=n$, and $k-1$ intermediate layers of nodes $V_1,V_2,\ldots,V_{k-1}$ with $|V_2|=\ldots=|V_{k}|=n-2$, each of which is a copy of nodes
$\{2,\ldots,n-1\}$:
\[
s \Rightarrow V_1 \Rightarrow V_2 \Rightarrow \cdots
\Rightarrow V_{k-1} \Rightarrow t\,.
\]
Edges go only from one layer to the next layer.
The edge going from the source node $s$ to the $i$-th node on the fist layer $V_1$ is a switch labeled by the variable $x_{s,i}$, and the edge going from the $i$-th node in the last layer $V_{k-1}$ to the target node $t$ is also a switch labeled by the variable $x_{i,t}$.
For every $i\neq j\in \{2,\ldots,n-1\}$, the $j$-th node on the
$(l+1)$-th layer $V_{l+1}$ is entered by a switch from the $i$-th node on the previous $l$-th layer $V_{l}$ and is labeled with the variable
$x_{i,j}$.
The resulting branching program has
$\leq kn^2$ switches in total.
$\Box$
The following consequence of tropical Markov's bound (Lemma 4.4(2))
shows
that this tropical $(\min,+)$ branching program is essentially optimal
(among all such branching programs for this problem).
Theorem A
Let $4\leq k\leq n-2$. Every $(\min,+)$ branching program solving the lightest $k$-walk problem on $K_n$ must
have at least a constant times $kn(n-k)$ switches.
Proof
We will use the following classical result
of Erdős and Gallai [1]: for $l\geq 1$, every
$m$-vertex graph with $\gt (l-1)m/2$ edges contains a path of length
$l$. Since $\binom{m}{2}-(l-1)m/2=m(m-l)/2$, this result can be
re-stated as:
For $l\geq 1$, at least $m(m-l)/2$ edges must be
removed from $K_m$ to destroy all paths of length $l$.
Note that this bound cannot be improved. Indeed, if $m=ql$ is a
multiple of $l$, then we can split the vertices of $K_m$ into $q$
disjoint sets of size $l$, and remove all edges lying between these
sets. The resulting graph has no paths of length $l$, and we have
removed only $\binom{q}{2}l^2=m(m-l)/2$ edges.
Now consider the minimization problem
\begin{equation}\label{eq:walk1}
f(x)= \min \left\{ x_{i_1,i_2}+ x_{i_2,i_3}+\cdots + x_{i_{k-2},i_{k-1}}\right\}\,,
\end{equation}
where the minimum is over
all walks $(i_1,\ldots,i_{k-1})$ of length
$l:=k-2$ in the complete graph $K_m$ on $m:=n-2$ nodes $\{2,\ldots,n-1\}$. The problem $f$ is a subproblem of the lightest $k$-walk problem when all $2(n-1)$ edges of $K_n$ incident with the vertex $1$ or with the vertex
$n$ of $K_n$ are given zero weight. It is thus enough to prove that every
$(\min,+)$ branching program solving the problem $f$ must
have at least a constant times $kn(n-k)$ switches.
We clearly have $f(\vec{1})\geq k-2$. To lower bound the width
$\Cut{f}$ of $f$, let $Y$ be a set of $|Y|=\Cut{f}$ variables of $f$
such that every sum of $f$ contains at least one of these
variables. Every path of length $l$ in $K_m$ is also a walk of
length $l$. So, for every path of length $l$ in $K_m$, there is a
sum in Eq. \eqref{eq:walk1} whose variables correspond to
the edges of that path. Thus, this sum must contain at least one variable
in $Y$. This means that removal from $K_m$ of all edges corresponding to
the variables in $Y$ destroys all paths of length $l$ in $K_m$. The Erdős-Gallai result gives
$\Cut{f}=|Y|\geq m(m-l)/2= (n-2)(n-k)/2$. Since $f(\vec{1})\geq
k-2$, Lemma 5.4(1) implies that every branching program
computing $f$ over the $(\min,+)$ semiring must have at least
$f(\vec{1})\cdot \Cut{f}$ switches, which is at least a constant
times $kn(n-k)$.
∎
Remark 1: Note that a slight modification of the BFM $(\min,+)$ branching program for the lightest $k$-walk problem can also solve
the lightest $s$-$t$ path problem in $K_n$: just set $k:=n$
and add rectifiers (non-labeled edges) between the $i$th node in one layer $V_l$ to the $i$th node in the next layer $V_{l+1}$. The resulting
branching program(3) has only $O(n^3)$ switches. Whether this branching program is also optimal among all $(\min,+)$ branching programs
for the lightest $s$-$t$ path problem remains, however, an open problem: the argument we used in the proof of Theorem A (based on the Erdős-Gallai result) does not work then anymore.
$\Box$
Remark 2:
Tropical branching programs $\Phi$ correspond to so-called skew tropical circuits $\Phi'$ where one of the two inputs to each addition $(+)$ gate is a variable. Namely, every switch $(u,v)$ in $\Phi$ labeled by a variable $x_i$ as an addition gate $v=u+x_i$ in $\Phi'$, every
rectifier $(u,v)$ (unlabeled edge) in $\Phi$ as addition gate $v=u+0$ in $\Phi'$; since such gates are fully redundant, we can assume that such gates are not present in $\Phi'$. Every node $v$ in $\Phi$ is a gate in $\Phi'$
performing a min or
max operation:
Thus, the number of switches in $\Phi$ is exactly the number of addition $(+)$ gates in the skew circuit $\Phi'$, while (unbounded fanin) $\min$ or $\max$ gates are "for free".
$\Box$
Jump back ☝
Jump back ☝
Jump back ☝