Roughly speaking, my question is:
How costly is to make a cyclic graph acyclic while preserving all simple $s$-$t$ paths?
Let $K_n$ be a complete undirected graph on vertices $\{0,1,\ldots,n+1\}$. (My apologies to purists: I should write $K_{n+2}$, but so is simpler.) By an $s$-$t$ path in $K_n$ we will mean a simple path from vertex $s=0$ to vertex $t=n+1$ (no repeated visits of vertices allowed). We want to represent these paths by $s$-$t$ paths in a DAG (directed acyclic graph) $G$ in the following sense. Each edge of $G$ is either unlabeled or is labeled by some edge of $K_n$. Multiple edges joining the same two vertices are allowed. A path $p$ in $G$ represents a path $q$ in $K_n$, if each edge of $q$ is a label of some edge of $p$, and each label of $p$ is an edge of $q$. The order of labels in $p$ is irrelevant, that is, it is enough that the path $q$ is represented as a set of edges, not as a sequence.
Example: An $s$-$t$ path $p$ = $s\xrightarrow{e_3} u_1 \xrightarrow{\phantom{e_3}} u_2 \xrightarrow{e_1} u_3 \xrightarrow{e_2} u_4 \xrightarrow{\phantom{e_3}} t$ in $G$ represents the path $q=(e_1,e_2,e_3)$ in $K_n$.
A path $p$ in $G$ contains a path $q$ in $K_n$, if every edge of $q$ appears (at least once) as a label along $p$.
Example: An $s$-$t$ path $p$ = $s\xrightarrow{e_3} u_1 \xrightarrow{\phantom{e_3}} u_2 \xrightarrow{e_1} u_3 \xrightarrow{e_5} u_4 \xrightarrow{e_2} u_5 \xrightarrow{\phantom{e_3}} u_6 \xrightarrow{e_1} t$ in $G$ contains the path $q=(e_1,e_2,e_3)$ in $K_n$.
Thus, $p$ represents $q$ if $p$ contains $q$, and the number of labels in $p$ equals the number of edges in $q$ (there is a 1-1 correspondence between labels and edges in $q$).
A DAG $G$ represents $K_n$ if
- Every $s$-$t$ path in $K_n$ is represented by some $s$-$t$ path in $G$.
- Every $s$-$t$ path in $G$ contains at least one $s$-$t$ path in $K_n$.
Let $f(n)$ be the smallest number of edges in a DAG representing $K_n$.
It is not difficult to show that
$f(n)=O(n^3)$.
The construction is inspired by the Bellman-Ford$\ast$ dynamic programming algorithm for the single-source all shortest paths problem. Take a DAG $G=(V,E)$ with $n^2+2$ vertices arranged into $n+2$ layers. The first (resp. last) layer consists of one vertex $s$ (resp. $t$), corresponding to the vertex $0$ (resp. $n+1$) of $K_n$. Each middle layer consists of $n$ vertices which are the copies of the vertices $\{1,\ldots,n\}$ of $K_n$. There is a directed edge from each $u_i$ on one layer to each vertex $v_j$ on the next layer. The edge $(u_i,v_j)$ with $i\neq j$ is labeled by the edge $\{i,j\}$ of $K_n$ (or by its length $x_{ij}$). The edges $(u_i,v_i)$ joining two copies of the same vertex of $K_n$ are unlabeled. Then paths from $s$ to the vertices on the $k$-th layer represent all paths of length at most $k$ from $0$ to all the vertices $1,\ldots,n$ in $K_n$. The obtained graph is in fact the subproblem graph of Bellman-Ford algorithm: if we let unlabeled edges in $G$ to have length $0$, then the minimum length of an $s$-$t$ path in $G$ is exactly the minimum length of an $s$-$t$ path in $K_n$ (under the lengths-assignment $x_{ij}$).
Question: Does $f(n)=\Omega(n^3)$?
Motivation: If the answer is YES, this would show that the Bellman-Ford is optimal in a wide class of DP algorithms. If the answer is NO, then we would have a better DP algorithm!
The second condition (2) is important: without it, $O(n^2)$ edges are already sufficient.
To see this, let $H_i$ for $i=0,1,\ldots,n$ be a DAG consisting of $n+2$ parallel edges from $u_i$ to $u_{i+1}$. The $j$-th edge for $j\leq n+1$ is labeled by the edge $x_{i,j}$ between $i$ and $j$ in $K_n$. The last edge is unlabeled. Let now $G=H_0\circ H_1\circ\cdots\circ H_n$ be the graph obtained by connecting these graphs sequentially. Let $s=u_0$ and $t=u_{n+1}$. The graph $G$ has only $O(n^2)$ edges.
Now, if $0=j_0\to j_1\to j_2\to\cdots\to j_k\to j_{k+1}=n+1$ is a simple $s$-$t$ path in $K_n$, then chose in each $H_{j_i}$ with $i\in\{0,1,\ldots,k\}$ the edge labeled by the edge $j_i\to j_{i+1}$, that is, by $x_{j_i,j_{i+1}}$. In all the remaining $H_j$'s chose the unlabeled edge. Then the obtained directed path in $G$ represents our path in $K_n$. Note however that $G$ does not satisfy condition (2): say the $s$-$t$ path in $G$ consisting of only unlabeled edges contains no $s$-$t$ path of $K_n$. Thus, $G$ cannot be turned into a DP algorithm.
Has anybody seen something similar (cost of turning cyclic graphs into acyclic) being dealt with?
Footnote$^{\ast}$ The Bellman-Ford-Moore algorithm for this problem takes as subproblems $f_k(j)$ = length of a shortest path from the source vertex $s=0$ to vertex $j$ using at most $k$ edges. The terminal values are the lengths $f_1(j)=x_{s,j}$ of edges incident to the source vertex. The DP recursion is: $f_k(j)$ = minimum of $f_{k-1}(j)$ and $f_{k-1}(i)+x_{ij}$ for all $i$.
EDIT (of 5.01.2013): Yuval Filmus reminded me about one related result of
Aaron Potechin showing that it is important to use DAGs (not undirected graphs) to have efficient representations. Namely, if $\vec{K}_n$ is a directed complete graph, and $G$ is an undirected graph representing all $s$-$t$ paths in $\vec{K}_n$, then $G$ must have $n^{\Omega(\log n)}$ edges. Intuitively, this holds "because" it is difficult to ensure condition (2), if $G$ is undirected: then every edge $\{u,v\}$ may be traversed (by an $s$-$t$ path in $G$) in both directions, but the label of $\{u,v\}$ can be consistent with only one of two directed edges $(i,j)$ and $(j,i)$ in $\vec{K}_n$. Potechin's result implies that monotone-$L$ $\neq$ monotone-$NL$. Note that, if we allow $G$ be directed, then the construction above gives a DAG with $O(n^3)$ edges representing $\vec{K}_n$.
NOTE [added 03.07.2018]: As noted by Neal Young, conditions (1) and (2) alone are not sufficient to get from $G$ a DP algorithm for the shortest s-t paths. For this, condition (1) must be strengthened to: every s-t path $p$ in $K_n$ is represented by some s-t path $q$ in $G$ in a read-once manner, that is, every edge of $p$ must appear along $q$ exactly once (as label). The graph $G$ arising from the Belman-Ford DP algorithm has this (stronger) property.
