Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

The following question is related to the optimality of the Bellman-Ford $s$-$t$ shortest path dynamic programming algorithm (see this post for a connection). Also, a positive answer would imply that the minimal size of a monotone nondeterministic branching program for the STCONN problem is $\Theta(n^3)$.

Let $G$ be a DAG (directed acyclic graph) with one source node $s$ and one target node $t$. A $k$-cut is a set of edges, whose removal destroys all $s$-$t$ paths of length $\geq k$; we assume that there are such paths in $G$. Note that shorter $s$-$t$ paths need not be destroyed.

Question: Does $G$ must have at least (about) $k$ disjoint $k$-cuts?

If there are no $s$-$t$ paths shorter than $k$, the answer is YES, because we have the following known min-max fact (a dual to Menger’s theorem) attributed to Robacker$\ast$. An $s$-$t$ cut is a $k$-cut for $k=1$ (destroys all $s$-$t$ paths).

Fact: In any directed graph, the maximum number of edge-disjoint $s$-$t$ cuts is equal to the minimum length of an $s$-$t$ path.

Note that this holds even if the graph is not acyclic.

Proof: Trivially, the minimum is at least the maximum, since each $s$-$t$ path intersects each $s$-$t$ cut in an edge. To see equality, let $d(u)$ be the length of a shortest path from $s$ to $u$. Let $U_r=\{u\colon d(u)=r\}$, for $r = 1,\ldots, d(t)$, and let $E_r$ be the set of edges leaving $U_r$. It is clear that the sets $E_r$ are disjoint, because the sets $U_r$ are such. So, it remains to show that each $E_r$ is an $s$-$t$ cut. To show this, take an arbitrary $s$-$t$ path $p=(u_1, u_2, \ldots,u_m)$ with $u_1=s$ and $u_m=t$. Since $d(u_{i+1})\leq d(u_i)+1$, the sequence of distances $d(u_1),\ldots,d(u_m)$ must reach the value $d(u_m)=d(t)$ by starting at $d(u_1)=d(s)=0$ and increasing the value by at most $1$ in each step. If some value $d(u_i)$ is decreased , then we must reach value $d(u_i)$ latter. So, there must be a $j$ where a jump from $d(u_j)=r$ to $d(u_{j+1})=r+1$ happens, meaning the edge $(u_j,u_{j+1})$ belongs to $E_r$, as desired. Q.E.D.

But what if there are also shorter (than $k$) paths? Any hint/reference?


$^{\ast}$ J.T. Robacker, Min-Max Theorems on Shortest Chains and Disjoint Cuts of a Network, Research Memorandum RM-1660, The RAND Corporation, Santa Monica, California, [12 Jan- uary] 1956.
EDIT (a day later): Via a short and very nice argument, David Eppstein answered the original question above in negative: the complete DAG $T_n$ (a transitive tournament) cannot have more than four disjoint $k$-cuts! In fact, he proves the following interesting structural fact, for $k$ about $\sqrt{n}$. A cut is pure if it contains no edges incident to $s$ or to $t$.

Every pure $k$-cut in $T_n$ contains a path of length $k$.

This, in particular, implies that every two pure $k$-cuts must intersect! But perhaps there still are many pure $k$-cuts that do not overlap "too much". Hence, a relaxed question (the consequences for STCONN would be the same):

Question 2: If every pure $k$-cut has $\geq M$ edges, does then the graph must have about $\Omega(k\cdot M)$ edges?

The connection with the complexity of STCONN comes from the result of Erdős and Gallai that one has to remove all but $(k-1)m/2$ edges from (undirected) $K_m$ in order to destroy all paths of length $k$.


EDIT 2: I now asked Question 2 at mathoverflow.

share|improve this question
add comment

1 Answer 1

up vote 9 down vote accepted

Short answer: no.

Let $G$ be a complete DAG (transitive tournament) on $n$ vertices with $s$ and $t$ its source and sink, and let $k=\sqrt{n/3}$. Observe that there can be at most four disjoint cuts that contain more tham $n/3$ edges incident to $s$ or more than $n/3$ edges incident to $t$. So, if there are to be many disjoint cuts, we can assume that there exists a cut $C$ that does not contain large numbers of edges incident to $s$ and $t$.

Now let $X$ be the complete subgraph induced in $G$ by the set of vertices $x$ such that edges $sx$ and $xt$ do not belong to $C$. The number of vertices in $X$ is at least $n/3$, because otherwise $C$ would touch too many edges incident to $s$ or $t$. However, $X\setminus C$ cannot contain a $k$-path, because if such a path existed it could be concatenated with $s$ and $t$ to form a long path in $G\setminus C$. Therefore, the longest-path layering of $X\setminus C$ has fewer than $k$ layers, and has a layer containing more than $(n/3)/k=k$ vertices. Since this is a layer of the longest path layering, it is independent in $X\setminus C$, and therefore complete in $C$, so $C$ contains a path $P$ through the vertices of this layer, of length $k$. This path must be disjoint from all of the other cuts.

Every cut that is not $C$ must contain either the edge from $s$ to the start of path $P$ or the edge from the end of path $P$ to $t$, or else it would not block the path $s$–$P$–$t$. So if $C$ exists, there can be at most three disjoint cuts. And if $C$ does not exist (that is, if all cuts cover more than $n/3$ edges incident to $s$ or to $t$) there can be at most four disjoint cuts. Either way, this is a lot fewer than $k$ cuts.

share|improve this answer
    
@ David: Interesting argument (albeit I have not quite understood it yet: why C must have a k-path). But where the argument fails (it should) if all s-t paths are long, of length at least k? –  Stasys Jan 17 '13 at 12:34
1  
@Stasys: G is a tournament, the proof uses this fact, so imo that is why it would fail. –  domotorp Jan 17 '13 at 12:53
    
@domotorp: thanks, indeed I missed the word "complete". I cannot find a flaw as yet, but this would be a rather counterintuitive fact: even if there are a lot of k-path in an acyclic tournament, we cannot select many disjoint systems of their representatives (edges). –  Stasys Jan 17 '13 at 14:13
    
@David: Actually, to have the mentioned consequences, we can allow that cuts are only "almost disjoint", i.e may share edges incident to s or t (we have only 2n these special edges). A real goal is to show that G must have about kN edges, if we know that every "pure" k-cut (without these special edges) must have N edges. Can your (very nice, as I now see) argument be modified to this ("almost disjoint") situation? –  Stasys Jan 17 '13 at 15:42
2  
If you allow cuts to share edges incident to s or t, then why can't you make all the cuts consist exactly of the set of edges incident to s? On the other hand, my argument shows that (with its choice of $G$ and $k$) there can be only one pure cut. –  David Eppstein Jan 17 '13 at 16:45
show 6 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.