\(
\def\<#1>{\left<#1\right>}
\let\geq\geqslant
\let\leq\leqslant
% an undirected version of \rightarrow:
\newcommand{\mathdash}{\relbar\mkern-9mu\relbar}
\def\deg#1{\mathrm{deg}(#1)}
\newcommand{\dg}[1]{d_{#1}}
\newcommand{\Norm}{\mathrm{N}}
\newcommand{\const}[1]{c_{#1}}
\newcommand{\cconst}[1]{\alpha_{#1}}
\newcommand{\Exp}[1]{E_{#1}}
\newcommand*{\ppr}{\mathbin{\ensuremath{\otimes}}}
\newcommand*{\su}{\mathbin{\ensuremath{\oplus}}}
\newcommand{\nulis}{\vmathbb{0}} %{\mathbf{0}}
\newcommand{\vienas}{\vmathbb{1}}
\newcommand{\Up}[1]{#1^{\uparrow}} %{#1^{\vartriangle}}
\newcommand{\Down}[1]{#1^{\downarrow}} %{#1^{\triangledown}}
\newcommand{\lant}[1]{#1_{\mathrm{la}}} % lower antichain
\newcommand{\uant}[1]{#1_{\mathrm{ua}}} % upper antichain
\newcommand{\skal}[1]{\langle #1\rangle}
\newcommand{\NN}{\mathbb{N}} % natural numbers
\newcommand{\RR}{\mathbb{R}}
\newcommand{\minTrop}{\mathbb{T}_{\mbox{\rm\footnotesize min}}}
\newcommand{\maxTrop}{\mathbb{T}_{\mbox{\rm\footnotesize max}}}
\newcommand{\FF}{\mathbb{F}}
\newcommand{\pRR}{\mathbb{R}_{\mbox{\tiny $+$}}}
\newcommand{\QQ}{\mathbb{Q}}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\gf}[1]{GF(#1)}
\newcommand{\conv}[1]{\mathrm{Conv}(#1)}
\newcommand{\vvec}[2]{\vec{#1}_{#2}}
\newcommand{\f}{{\mathcal F}}
\newcommand{\h}{{\mathcal H}}
\newcommand{\A}{{\mathcal A}}
\newcommand{\B}{{\mathcal B}}
\newcommand{\C}{{\mathcal C}}
\newcommand{\R}{{\mathcal R}}
\newcommand{\MPS}[1]{f_{#1}} % matrix multiplication
\newcommand{\ddeg}[2]{\#_{#2}(#1)}
\newcommand{\length}[1]{|#1|}
\DeclareMathOperator{\support}{sup}
\newcommand{\supp}[1]{\support(#1)}
\DeclareMathOperator{\Support}{sup}
\newcommand{\spp}{\Support}
\newcommand{\Supp}[1]{\mathrm{Sup}(#1)} %{\mathcal{S}_{#1}}
\newcommand{\lenv}[1]{\lfloor #1\rfloor}
\newcommand{\henv}[1]{\lceil#1\rceil}
\newcommand{\homm}[2]{{#1}^{\langle #2\rangle}}
\let\daug\odot
\let\suma\oplus
\newcommand{\compl}[1]{Y_{#1}}
\newcommand{\pr}[1]{X_{#1}}
\newcommand{\xcompl}[1]{Y'_{#1}}
\newcommand{\xpr}[1]{X'_{#1}}
\newcommand{\cont}[1]{A_{#1}} % content
\def\fontas#1{\mathsf{#1}} %{\mathrm{#1}} %{\mathtt{#1}} %
\newcommand{\arithm}[1]{\fontas{Arith}(#1)}
\newcommand{\Bool}[1]{\fontas{Bool}(#1)}
\newcommand{\linBool}[1]{\fontas{Bool}_{\mathrm{lin}}(#1)}
\newcommand{\rBool}[2]{\fontas{Bool}_{#2}(#1)}
\newcommand{\BBool}[2]{\fontas{Bool}_{#2}(#1)}
\newcommand{\MMin}[1]{\fontas{Min}(#1)}
\newcommand{\MMax}[1]{\fontas{Max}(#1)}
\newcommand{\negMin}[1]{\fontas{Min}^{-}(#1)}
\newcommand{\negMax}[1]{\fontas{Max}^{-}(#1)}
\newcommand{\Min}[2]{\fontas{Min}_{#2}(#1)}
\newcommand{\Max}[2]{\fontas{Max}_{#2}(#1)}
\newcommand{\convUn}[1]{\fontas{L}_{\ast}(#1)}
\newcommand{\Un}[1]{\fontas{L}(#1)}
\newcommand{\kUn}[2]{\fontas{L}_{#2}(#1)}
\newcommand{\Nor}{\mu} % norm without argument
\newcommand{\nor}[1]{\Nor(#1)}
\newcommand{\bool}[1]{\hat{#1}} % Boolean version of f
\newcommand{\bphi}{\phi} % boolean circuit
\newcommand{\xf}{\boldsymbol{\mathcal{F}}}
\newcommand{\euler}{\mathrm{e}}
\newcommand{\ee}{f} % other element
\newcommand{\exchange}[3]{{#1}-{#2}+{#3}}
\newcommand{\dist}[2]{{#2}[#1]}
\newcommand{\Dist}[1]{\mathrm{dist}(#1)}
\newcommand{\mdist}[2]{\dist{#1}{#2}} % min-max dist.
\newcommand{\matching}{\mathcal{M}}
\renewcommand{\E}{A}
\newcommand{\F}{\mathcal{F}}
\newcommand{\set}{W}
\newcommand{\Deg}[1]{\mathrm{deg}(#1)}
\newcommand{\mtree}{MST}
\newcommand{\stree}{{\cal T}}
\newcommand{\dstree}{\vec{\cal T}}
\newcommand{\Rich}{U_0}
\newcommand{\Prob}[1]{\ensuremath{\mathrm{Pr}\left\{{#1}\right\}}}
\newcommand{\xI}{\boldsymbol{I}}
\newcommand{\plus}{\mbox{\tiny $+$}}
\newcommand{\sgn}[1]{\left[#1\right]}
\newcommand{\ccompl}[1]{{#1}^*}
\newcommand{\contr}[1]{[#1]}
\newcommand{\harm}[2]{{#1}\,\#\,{#2}} %{{#1}\,\oplus\,{#2}}
\newcommand{\hharm}{\#} %{\oplus}
\newcommand{\rec}[1]{1/#1}
\newcommand{\rrec}[1]{{#1}^{-1}}
\DeclareRobustCommand{\bigO}{%
\text{\usefont{OMS}{cmsy}{m}{n}O}}
\newcommand{\dalyba}{/}%{\oslash}
\newcommand{\mmax}{\mbox{\tiny $\max$}}
\newcommand{\thr}[2]{\mathrm{Th}^{#1}_{#2}}
\newcommand{\rectbound}{h}
\newcommand{\pol}[3]{\sum_{#1\in #2}{#3}_{#1}\prod_{i=1}^n x_i^{#1_i}}
\newcommand{\tpol}[2]{\min_{#1\in #2}\left\{\skal{#1,x}+\const{#1}\right\}}
\newcommand{\comp}{\circ} % composition
\newcommand{\0}{\vec{0}}
\newcommand{\drops}[1]{\tau(#1)}
\newcommand{\HY}[2]{F^{#2}_{#1}}
\newcommand{\hy}[1]{f_{#1}}
\newcommand{\hh}{h}
\newcommand{\hymin}[1]{f_{#1}^{\mathrm{min}}}
\newcommand{\hymax}[1]{f_{#1}^{\mathrm{max}}}
\newcommand{\ebound}[2]{\partial_{#2}(#1)}
\newcommand{\Lpure}{L_{\mathrm{pure}}}
\newcommand{\Vpure}{V_{\mathrm{pure}}}
\newcommand{\Lred}{L_1} %L_{\mathrm{red}}}
\newcommand{\Lblue}{L_0} %{L_{\mathrm{blue}}}
\newcommand{\epr}[1]{z_{#1}}
\newcommand{\wCut}[1]{w(#1)}
\newcommand{\cut}[2]{w_{#2}(#1)}
\newcommand{\Length}[1]{l(#1)}
\newcommand{\Sup}[1]{\mathrm{Sup}(#1)}
\newcommand{\ddist}[1]{d_{#1}}
\newcommand{\sym}[2]{S_{#1,#2}}
\newcommand{\minsum}[2]{\mathrm{MinS}^{#1}_{#2}}
\newcommand{\maxsum}[2]{\mathrm{MaxS}^{#1}_{#2}} % top k-of-n function
\newcommand{\cirsel}[2]{\Phi^{#1}_{#2}} % its circuit
\newcommand{\sel}[2]{\sym{#1}{#2}} % symmetric pol.
\newcommand{\cf}[1]{{#1}^{o}}
\newcommand{\Item}[1]{\item[\mbox{\rm (#1)}]} % item in roman
\newcommand{\bbar}[1]{\underline{#1}}
\newcommand{\Narrow}[1]{\mathrm{Narrow}(#1)}
\newcommand{\Wide}[1]{\mathrm{Wide}(#1)}
\newcommand{\eepsil}{\varepsilon}
\newcommand{\amir}{\varphi}
\newcommand{\mon}[1]{\mathrm{mon}(#1)}
\newcommand{\mmon}{\alpha}
\newcommand{\gmon}{\alpha}
\newcommand{\hmon}{\beta}
\newcommand{\nnor}[1]{\|#1\|}
\newcommand{\inorm}[1]{\left\|#1\right\|_{\mbox{\tiny $\infty$}}}
\newcommand{\mstbound}{\gamma}
\newcommand{\coset}[1]{\textup{co-}{#1}}
\newcommand{\spol}[1]{\mathrm{ST}_{#1}}
\newcommand{\cayley}[1]{\mathrm{C}_{#1}}
\newcommand{\SQUARE}[1]{\mathrm{SQ}_{#1}}
\newcommand{\STCONN}[1]{\mathrm{STCON}_{#1}}
\newcommand{\STPATH}[1]{\mathrm{PATH}_{#1}}
\newcommand{\SSSP}[1]{\mathrm{SSSP}(#1)}
\newcommand{\APSP}[1]{\mathrm{APSP}(#1)}
\newcommand{\MP}[1]{\mathrm{MP}_{#1}}
\newcommand{\CONN}[1]{\mathrm{CONN}_{#1}}
\newcommand{\PERM}[1]{\mathrm{PER}_{#1}}
\newcommand{\mst}[2]{\tau_{#1}(#2)}
\newcommand{\MST}[1]{\mathrm{MST}_{#1}}
\newcommand{\MIS}{\mathrm{MIS}}
\newcommand{\dtree}{\mathrm{DST}}
\newcommand{\DST}[1]{\dtree_{#1}}
\newcommand{\CLIQUE}[2]{\mathrm{CL}_{#1,#2}}
\newcommand{\ISOL}[1]{\mathrm{ISOL}_{#1}}
\newcommand{\POL}[1]{\mathrm{POL}_{#1}}
\newcommand{\ST}[1]{\ptree_{#1}}
\newcommand{\Per}[1]{\mathrm{per}_{#1}}
\newcommand{\PM}{\mathrm{PM}}
\newcommand{\error}{\epsilon}
\newcommand{\PI}[1]{A_{#1}}
\newcommand{\Low}[1]{A_{#1}}
\newcommand{\node}[1]{v_{#1}}
\newcommand{\BF}[2]{W_{#2}[#1]} % Bellman-Ford
\newcommand{\FW}[3]{W_{#1}[#2,#3]} % Floyd-Washall
\newcommand{\HK}[1]{W[#1]} % Held-Karp
\newcommand{\WW}[1]{W[#1]}
\newcommand{\pWW}[1]{W^{+}[#1]}
\newcommand{\nWW}[1]{W^-[#1]}
\newcommand{\knap}[2]{W_{#2}[#1]}
\newcommand{\Cut}[1]{w(#1)}
\newcommand{\size}[1]{\mathrm{size}(#1)}
\newcommand{\dual}[1]{{#1}^{\ast}}
\def\gcd#1{\mathrm{gcd}(#1)}
\newcommand{\stein}[1]{\mathrm{STEIN}(#1)}
\)
[This is a supplementary material to Chapter 1, Section 1.4]
A pure DP algorithm for the minimum weight Steiner tree problem
We are given an undirected connected graph $G=(V,E)$ on $|V|=n$ nodes, and a subset $Y\subseteq V$ of nodes, called terminals.
A Steiner tree for $Y$ (named after the Swiss mathematician Jacob Steiner) is a tree $T$ in $G$ containing all terminals.
That is, every two terminals are connected by a path in the tree $T$. For example, a graph $G$ with $6$ nodes and $|Y|=4$ terminals $(\bullet)$, as well as a Steiner tree in $G$ for these terminals:
Given a subset $Y\subseteq V$ of $|Y|=t$ terminals, the minimum weight Steiner tree problem $\stein{n,Y}$ is, given an assignment $x:E\to\RR_+$ of nonnegative weights to the edges of $G$, to find a Steiner tree $T$ for $Y$ of minimal weight $x(T)=\sum_{e\in T}x(e)$ (we view a tree $T$ as the set of its edges). Note that (since the weights are nonnegative) every leaf of an optimal Steiner tree $T$ (a node of degree $1$ in $T$) must
be a terminal, but the tree $T$ may contain non-terminals as well.
In particular, for any set $Y=\{s,t\}$ of two terminals $s$ and $t$, the problem $\stein{n,Y}$ is the shortest $s$-$t$ path problem, and can be solved by a $(\min,+)$ circuit of size $O(n^3)$ (see Example 1.7 in the book). On the other extreme, when all nodes are terminals (i.e., when $Y=V$), then $\stein{n,Y}$ is the MST problem (minimum weight spanning tree problem): compute the minimum weight of a tree containing all nodes of $G$. By Theorem 3.16 in the book, the MST problem on the complete graph $G=K_n$ requires $(\min,+)$ circuits of size $2^{\Omega(\sqrt{n})}$,
but can be solved on any $n$-vertex graph $G$ by a $(\min,\max,+)$ circuit (with both $\min$ and $\max$ operations allowed as gates) of size $O(n^3)$ (Theorem 6.5 in the book).
For any other set $Y\subseteq V$ of $|Y|=t$ terminals, the Dreyfus-Levin-Wagner pure DP algorithm [1,2] solves $\stein{n,Y}$ using $O(n^3+3^tn+2^tn^2)$ operations. Note that for any constant (and even logarithmic) number $t$ of terminals, this is only $O(n^3)$ operations.
The idea is to recursively solve the following subproblems
for all pairs $(X,v)$ with $X\subseteq Y$ and $v\in V$:
\begin{align*}
s_v(X) &:= \mbox{ min weight of a Steiner tree $T$ for the set $X+v$ of terminals,}
\end{align*}
where $X+v$ stands for $X\cup\{v\}$ (in particular, $X+v=X$ if $v\in X$).
What we want to compute is $s_v(Y)$ for any (fixed) terminal $v\in Y$. Clearly, for every two nodes $u\neq v\in V$, we have
$s_v(\{u\})=s_u(\{v\})=d(u,v)$, where $d(u,v)$ is the minimum weight of a path in $G$ between $u$ and $v$, with $d(v,v)=0$ for convenience.
In general, let $T=T[X+v]$ be an optimal Steiner tree for the set $X+v$ of terminals. A ``generic'' case is when the new terminal $v$ is a leaf of $T$, and $v$ is joined by a lightest path $P_{v,w}$ to an interior node $w\in V(T)$ of degree $\geq 3$. The node $w$ splits the tree $T\setminus P_{v,w}$ into two parts, namely $T[X'+w]$ and $T[X''+w]$
for some nontrivial partition $X=X'\cup X''$ of the set $X$. We thus have a recurrence
\[
s_v(X)=\min_{w\in V}\Big\{d(v,w)+\min_{\emptyset\neq X'\subsetneq X}\big\{s_w(X')+s_w(X\setminus X')\big\}\Big\}\,.
\]
The recurrence is also valid in the ``non-generic'' cases, when the new terminal $v$ is not a leaf of $T$ (take $w=v$, then $d(v,w)=0$) or when $v$ is joined by the path $P_{v,w}$ to a leaf of $T[X]$, that is, when $w$ has only degree two in $T[X+v]$ (take $X'=\{w\}$ in this case).
For each set $Y\subseteq V$ of $|Y|=t$ terminals, the total number of gates in the resulting tropical $(\min,+)$ circuit is $O(n^3+3^tn+2^tn^2)$: we use $O(n^3)$ operations to compute all distances $d(u,v)$ using the Roy-Floyd-Warshall DP algorithm (Example 1.8 in the book), there are at most $n\sum_{i=0}^t\binom{t}{i}2^i=n3^t$ possibilities to chose a set $X+v$ and its partition $X=X'\cup X''$,
and we need only $O(2^tn^2)$ operations to implement the recursion for $s_v(X)$.
References:
- Dreyfus, S., Wagner, R.: The Steiner problem in graphs. Networks 1(3), 195–207 (1971) local copy
- Levin, A.: Algorithm for the shortest connection of a group of graph vertices. Sov. Math. Dokl. 12, 1477–1481 (1971)
S. Jukna, September 2023
⇦ Back to the comments