<p>Roughly speaking, my question is:</p>

<blockquote>
How costly is to make a <b>cyclic</b> graph
<b>acyclic</b> while preserving all simple $s$-$t$ paths?
</blockquote>

<p>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$ <b>path</b> 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 <b>acyclic</b> 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$ <b>represents</b>
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 <b>set</b> of edges, not as a <b>sequence</b>.
<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_2} u_4 \xrightarrow{\phantom{e_3}} t$ in $G$ represents the path
$q=(e_1,e_2,e_3)$ in $K_n$.
<p>
A path $p$ in $G$ <b>contains</b> a path $q$ in $K_n$, if every edge of $q$ appears (at least
once) as a label along $p$.
<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$.
<p></p>

<p>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$).
<p>
A DAG $G$ <b>represents</b> $K_n$ if</p>

<ol>
<li>Every $s$-$t$ path in $K_n$ is represented by some $s$-$t$ path in $G$.</li>
<li>Every $s$-$t$ path in $G$ contains at least one $s$-$t$ path in $K_n$.</li>
</ol>

<p><p>
Let $f(n)$ be the smallest number of edges in a DAG representing $K_n$.<br>
It is not difficult to show that
$f(n)=O(n^3)$.
<p>
<img src="https://i.sstatic.net/W3mAE.jpg" alt="The Bellman-Ford graph">
<p>
The construction is inspired by the Bellman-Ford<sup>$\ast$</sup> 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}$).</p>

<blockquote>
<b>Question: &nbsp;&nbsp;</b>Does $f(n)=\Omega(n^3)$?
</blockquote>

<p><b> Motivation:</b>
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!</p>

<p><hr>
The second condition (2) is important:
without it, $O(n^2)$ edges are already sufficient.
<p>
<img src="https://i.sstatic.net/Skc0U.jpg" alt="Necessity of condition (2)">
<p>
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.
<p>
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.</p>

<blockquote>
Has anybody seen something similar
(cost of turning cyclic graphs into acyclic) being dealt with?
</blockquote>

<p><hr>
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$.

<hr>
<b>EDIT</b> (of 5.01.2013): Yuval Filmus reminded me about one related
<a href="http://eccc.hpi-web.de/report/2009/142/" rel="noreferrer">result</a> of<br>
Aaron Potechin showing that it is important to use DAGs (not undirected graphs)
to have efficient representations. Namely, if $\vec{K}_n$ is a <b>directed</b>
complete graph, and $G$ is an  <b>undirected</b> 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 <i>both</i> 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 <b>directed</b>, then
the construction above gives a
DAG with $O(n^3)$ edges representing  $\vec{K}_n$.
<hr>
<b>NOTE</b> [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 <i>read-once</i> 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.</p>

CC BY-SA 3.0
2012-12-04T10:43:24.677Z
Still working on grokking the details of your problems, but the initial summary seems misleading. It sounds like what you're trying to do is to take an arbitrary $s$–$t$-graph and eliminate its cycles without disturbing any simple $s$–$t$-paths. This could be used to solve the shortest path problems in the presence of negative cycles (by first removing the cycles, and then solving the SP problem), which is NP-hard—which would make your problem NP-hard (which I'm sure it's not)…
Magnus Lie Hetland
CC BY-SA 3.0
2012-12-04T11:33:01.323Z
@Magnus: Thanks for the comment. Note however that in K_n we cannot remove any single edge, because then we will loose all simple s-t paths through that edge. What Bellman-Ford do is they rather *direct* the edges, take multiple copies of them, and allow unmarked edges to represent s-t paths of all lengths. These multiple copies allow to even preserve the order of edges in the paths. Thus, my question actually is: can one do better than Bellman-Ford if one allows the edges of a path be represented in *any* order?
Stasys
CC BY-SA 3.0
2012-12-06T02:41:56.790Z
complex but intriguing. is this all assuming the graph has no negative cycle? is there some/any constraint on the edge weights, ie positive, negative, mixed?
vzn
CC BY-SA 3.0
2012-12-06T11:57:49.720Z
@vzn: The question itself is for *unweighted* $K_n$. The Bellman-Ford DAG $G$ above represents all simple s-t paths in K_n of length at most $n+1$. Thus, $G$ is also a DP algorithm solving the shortest s-t path problem in K_n under all weigt-assignments producing no negative cycles. We only want to understand whether Bellman-Ford is optimal on problem instances on which it *works* (no negative cycles). This happens iff  any DAG representing all simple s-t paths of length $\leq n+1$ in (unweighted) $K_n$ must have $\Omega(n^3)$ edges (this "iff" can be shown by using only 0 and 1 as weights).
Stasys
CC BY-SA 3.0
2012-12-06T15:44:35.433Z
1st you say $K_n$ is unweighted and then you seem to say its edges are weighted either 0/1...? re wikipedia, [dijkstras algorithm](http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) is faster if there are no nonnegative edge weights & "thus bellman ford is primarily used for graphs with negative edge weights"
vzn
CC BY-SA 3.0
2012-12-06T17:39:39.890Z
@vzn: A good point, thanks! Indeed, I should be more careful with my "motivation" of the purely graph-theoretic *unweighted* problem. My motivation was to prove/disprove that Bellman-Ford is optimal among *DP algorithms*. But is Dijkstra a "pure" DP algorithm? I mean, can it be given by a simple recursive relation? (Min of values of subproblems plus edge-lengths, as in the case of Bellman-Floyd. With no if-then-else comparisons of intermediate values.) Can Dijkstra be presented as solving the shortest path problem in a DAG?
Stasys
CC BY-SA 3.0
2012-12-06T18:03:52.143Z
all honesty, from what little understood so far, think its a creative angle & would like to dig into it with many more questions but one could easily imagine an entire paper proving the significantly noteworthy result if it holds, right? therefore alas it may not really be a great fit for this particular forum (and alas also there is no other place remotely like TCS.se elsewhere in cyberspace where it could fit better.. maybe a blog?)... would be interested in engaging in extended chat room discussion on the problem...
vzn
CC BY-SA 3.0
2012-12-06T19:09:38.223Z
@vzn: Yes, the answer NO to my question (much fewer than $n^3$ edges in a DAG are enough, if the order of edges must not be preserved) would be worth even a paper. But I believe this is true only $< 0.1\%$. So, a YES answer would receive less attention. I am trying to figure out how to start a chat on this question. (Am new both in stackexchange as well as in algorithmics.)
Stasys
CC BY-SA 3.0
2012-12-06T19:36:20.470Z
let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/6645/discussion-between-vzn-and-stasys)
vzn
CC BY-SA 3.0
2012-12-17T14:04:59.127Z
@Stasys As for interpreting Dijkstra as a DP algorithm, it maybe useful for you to check [Dijkstra in DP](http://matwbn.icm.edu.pl/ksiazki/cc/cc35/cc3536.pdf), which uses the _DP functional equation_ like $f(j) = \min_i \big(f(i) + D(i,j) \big)$ and applies the _successive approximation methods_ to solve it. However, I am not sure whether it is a "pure" DP algorithm as you required.
hengxin
CC BY-SA 3.0
2012-12-25T16:38:30.947Z
@hengxin: Sorry for the delay. I know that paper. But "Dijkstra's DP" is "double dynamic": the set B(j) of predecessors of j is determined by the *current* accumulated distance (successive approximation). In this sense, it is not "pure" DP, as Bellman-Ford or Floyd-Warschal are.
Stasys
CC BY-SA 3.0
2013-01-01T08:07:40.080Z
Aaron Potechin proved that $f(n) = n^{\Theta(\log n)}$ for the undirected version, see http://eccc.hpi-web.de/report/2009/142/.
Yuval Filmus
CC BY-SA 3.0
2013-01-01T19:52:25.727Z
@Youval: Thanks for pointing to this. I should have had mentioned this quite surprising result. To my knowledge, this is the first so strong separation between directed and undirected switching network models. So, it is important that paths in the representing DAG (as well as in DP algorithms) are not reversible.
Stasys
CC BY-SA 3.0
2014-02-19T03:38:18.857Z
hi SJ ... as you know, awhile back suggested/discussed NFA type approaches to this problem in chat at length. recently ran across this new paper that seems to have results that use this technique on a similar problem: [Relations between automata and the simple k-path problem](http://arxiv.org/abs/1401.5707) Ben-Basat/Gabizon. what do you think? anywhere near an answer?
vzn
CC BY-SA 4.0
2018-07-02T15:17:14.323Z
As you've stated your problem, a path $p$ in $K_n$ may be represented by a path $q$ in $G$ such that some edges on $p$ occur more than once as labels in $q$.  E.g.  
$s
\xrightarrow{e_3} u_1
\xrightarrow{\phantom{e_3}} u_2
\xrightarrow{e_1} u_3
\xrightarrow{e_2} u_4
\xrightarrow{e_1} u_5
\xrightarrow{\phantom{e_3}} t$ 
in $G$ represents the path
$q=(e_1,e_2,e_3)$ in $K_n$.  
Further, it may be that, for every representation $q$ of $p$ in $G$, some edge in $p$ occurs more than once as a label in $q$.  If this is true, then the associated DP might not compute shortest paths, right?
Neal Young
CC BY-SA 4.0
2018-07-03T11:00:59.677Z
@Neal Young: yes, you are right, thanks for pointing to this. I now added a note at the end.
Stasys
CC BY-SA 4.0
2020-02-15T01:55:44.653Z
Can you clarify more precisely the relation you have in mind of the graph to a dynamic program?  E.g. do you have in mind that each node in the graph represents a subproblem in the dynamic program, and should such a subproblem always be the shortest s-to-v distance for some vertex v among some subset of possible s-to-v paths?  Or, to be more precise, how exactly would you get from a given $G$ to a particular dynamic program (presumably for  shortest s-t path for the corresponding edge-weighted $K_n$)?
Neal Young
CC BY-SA 4.0
2020-02-15T10:42:22.493Z
Under a "DAG representing K_n" I meant a monotone switching-and-rectifier network over the (min,+) semiring. I've suggested one "DP like" model [here](https://doi.org/10.1007/s00453-013-9747-6).  Although the network of Bellman-Ford has this "noded = subproblems" property, it does not need to be present in general networks. Bellman-Ford's network (1st picture above) has this property, and actually considers all *walks* (not just paths). In the meanwhile, we have [shown](https://doi.org/10.1016/j.tcs.2016.03.014) that the Bellman-Ford's network is optimal.
Stasys
<graph-theory><lower-bounds><directed-acyclic-graph><dynamic-programming><shortest-path>
Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?
Stasys
# Combinatorics of Bellman-Ford or how to make cyclic graphs acyclic?

(Asked by: username_0 on 2012-12-03)

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

1. Every $s$-$t$ path in $K\_n$ is represented by some $s$-$t$ path in $G$.
2. 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 Bellman-Ford graph](https://i.sstatic.net/W3mAE.jpg)

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.

![Necessity of condition (2)](https://i.sstatic.net/Skc0U.jpg)

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](http://eccc.hpi-web.de/report/2009/142/) 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.

**Tags:** graph-theory, lower-bounds, directed-acyclic-graph, dynamic-programming, shortest-path
> **Comments:**
> **username_1**: Still working on grokking the details of your problems, but the initial summary seems misleading. It sounds like what you're trying to do is to take an arbitrary $s$–$t$-graph and eliminate its cycles without disturbing any simple $s$–$t$-paths. This could be used to solve the shortest path problems in the presence of negative cycles (by first removing the cycles, and then solving the SP problem), which is NP-hard—which would make your problem NP-hard (which I'm sure it's not)…  
> **username_0**: @Magnus: Thanks for the comment. Note however that in K_n we cannot remove any single edge, because then we will loose all simple s-t paths through that edge. What Bellman-Ford do is they rather *direct* the edges, take multiple copies of them, and allow unmarked edges to represent s-t paths of all lengths. These multiple copies allow to even preserve the order of edges in the paths. Thus, my question actually is: can one do better than Bellman-Ford if one allows the edges of a path be represented in *any* order?  
> **username_2**: complex but intriguing. is this all assuming the graph has no negative cycle? is there some/any constraint on the edge weights, ie positive, negative, mixed?  
> **username_0**: @vzn: The question itself is for *unweighted* $K_n$. The Bellman-Ford DAG $G$ above represents all simple s-t paths in K_n of length at most $n+1$. Thus, $G$ is also a DP algorithm solving the shortest s-t path problem in K_n under all weigt-assignments producing no negative cycles. We only want to understand whether Bellman-Ford is optimal on problem instances on which it *works* (no negative cycles). This happens iff  any DAG representing all simple s-t paths of length $\leq n+1$ in (unweighted) $K_n$ must have $\Omega(n^3)$ edges (this "iff" can be shown by using only 0 and 1 as weights).  
> **username_2**: 1st you say $K_n$ is unweighted and then you seem to say its edges are weighted either 0/1...? re wikipedia, [dijkstras algorithm](http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm) is faster if there are no nonnegative edge weights & "thus bellman ford is primarily used for graphs with negative edge weights"  
> **username_0**: @vzn: A good point, thanks! Indeed, I should be more careful with my "motivation" of the purely graph-theoretic *unweighted* problem. My motivation was to prove/disprove that Bellman-Ford is optimal among *DP algorithms*. But is Dijkstra a "pure" DP algorithm? I mean, can it be given by a simple recursive relation? (Min of values of subproblems plus edge-lengths, as in the case of Bellman-Floyd. With no if-then-else comparisons of intermediate values.) Can Dijkstra be presented as solving the shortest path problem in a DAG?  
> **username_2**: all honesty, from what little understood so far, think its a creative angle & would like to dig into it with many more questions but one could easily imagine an entire paper proving the significantly noteworthy result if it holds, right? therefore alas it may not really be a great fit for this particular forum (and alas also there is no other place remotely like TCS.se elsewhere in cyberspace where it could fit better.. maybe a blog?)... would be interested in engaging in extended chat room discussion on the problem...  
> **username_0**: @vzn: Yes, the answer NO to my question (much fewer than $n^3$ edges in a DAG are enough, if the order of edges must not be preserved) would be worth even a paper. But I believe this is true only $< 0.1\%$. So, a YES answer would receive less attention. I am trying to figure out how to start a chat on this question. (Am new both in stackexchange as well as in algorithmics.)  
> **username_2**: let us [continue this discussion in chat](http://chat.stackexchange.com/rooms/6645/discussion-between-vzn-and-stasys)  
> **username_3**: @Stasys As for interpreting Dijkstra as a DP algorithm, it maybe useful for you to check [Dijkstra in DP](http://matwbn.icm.edu.pl/ksiazki/cc/cc35/cc3536.pdf), which uses the _DP functional equation_ like $f(j) = \min_i \big(f(i) + D(i,j) \big)$ and applies the _successive approximation methods_ to solve it. However, I am not sure whether it is a "pure" DP algorithm as you required.  
> **username_0**: @hengxin: Sorry for the delay. I know that paper. But "Dijkstra's DP" is "double dynamic": the set B(j) of predecessors of j is determined by the *current* accumulated distance (successive approximation). In this sense, it is not "pure" DP, as Bellman-Ford or Floyd-Warschal are.  
> **username_4**: Aaron Potechin proved that $f(n) = n^{\Theta(\log n)}$ for the undirected version, see http://eccc.hpi-web.de/report/2009/142/.  
> **username_0**: @Youval: Thanks for pointing to this. I should have had mentioned this quite surprising result. To my knowledge, this is the first so strong separation between directed and undirected switching network models. So, it is important that paths in the representing DAG (as well as in DP algorithms) are not reversible.  
> **username_2**: hi SJ ... as you know, awhile back suggested/discussed NFA type approaches to this problem in chat at length. recently ran across this new paper that seems to have results that use this technique on a similar problem: [Relations between automata and the simple k-path problem](http://arxiv.org/abs/1401.5707) Ben-Basat/Gabizon. what do you think? anywhere near an answer?  
> **username_5**: As you've stated your problem, a path $p$ in $K_n$ may be represented by a path $q$ in $G$ such that some edges on $p$ occur more than once as labels in $q$.  E.g.   $s \xrightarrow{e_3} u_1 \xrightarrow{\phantom{e_3}} u_2 \xrightarrow{e_1} u_3 \xrightarrow{e_2} u_4 \xrightarrow{e_1} u_5 \xrightarrow{\phantom{e_3}} t$  in $G$ represents the path $q=(e_1,e_2,e_3)$ in $K_n$.   Further, it may be that, for every representation $q$ of $p$ in $G$, some edge in $p$ occurs more than once as a label in $q$.  If this is true, then the associated DP might not compute shortest paths, right?  
> **username_0**: @Neal Young: yes, you are right, thanks for pointing to this. I now added a note at the end.  
> **username_5**: Can you clarify more precisely the relation you have in mind of the graph to a dynamic program?  E.g. do you have in mind that each node in the graph represents a subproblem in the dynamic program, and should such a subproblem always be the shortest s-to-v distance for some vertex v among some subset of possible s-to-v paths?  Or, to be more precise, how exactly would you get from a given $G$ to a particular dynamic program (presumably for  shortest s-t path for the corresponding edge-weighted $K_n$)?  
> **username_0**: Under a "DAG representing K_n" I meant a monotone switching-and-rectifier network over the (min,+) semiring. I've suggested one "DP like" model [here](https://doi.org/10.1007/s00453-013-9747-6).  Although the network of Bellman-Ford has this "noded = subproblems" property, it does not need to be present in general networks. Bellman-Ford's network (1st picture above) has this property, and actually considers all *walks* (not just paths). In the meanwhile, we have [shown](https://doi.org/10.1016/j.tcs.2016.03.014) that the Bellman-Ford's network is optimal.  

---

## 0 answers

