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

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)

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.

  • 1
    $\begingroup$ 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)… $\endgroup$ – Magnus Lie Hetland Dec 4 '12 at 10:43
  • 2
    $\begingroup$ 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? $\endgroup$ – vzn Dec 6 '12 at 2:41
  • 1
    $\begingroup$ @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). $\endgroup$ – Stasys Dec 6 '12 at 11:57
  • 2
    $\begingroup$ 1st you say $K_n$ is unweighted and then you seem to say its edges are weighted either 0/1...? re wikipedia, dijkstras algorithm is faster if there are no nonnegative edge weights & "thus bellman ford is primarily used for graphs with negative edge weights" $\endgroup$ – vzn Dec 6 '12 at 15:44
  • 1
    $\begingroup$ @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? $\endgroup$ – Stasys Dec 6 '12 at 17:39

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.