32
$\begingroup$

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.

$\endgroup$
18
  • 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$ Dec 4, 2012 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, 2012 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, 2012 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, 2012 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, 2012 at 17:39

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.