11

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.
Community
  • 1
Stasys
  • 6,765
  • 29
  • 54

1 Answers1

9

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.

David Eppstein
  • 50,990
  • 3
  • 170
  • 278
  • @ 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
  • @David: I cannot see why your argument shows that there can be only one pure k-cut, because now we allow that cuts can share the edge s->P and/or P->t. Am I missing something? I don't want to take just edges leaving s - the goal is to show that G must have many edges if there are many pure k-cuts. – Stasys Jan 17 '13 at 17:45
  • You defined a pure cut to be a cut that has no special edges, right? So it would fit the criteria of the cut $C$ in my argument. – David Eppstein Jan 17 '13 at 21:51
  • Yes, you are right: any other pure k-cut must intersect C. A nice fact! But what about the relaxed Question 2? That is, knowing that each k-cut must have N edges, can we then conclude that there must be at least about k times N edges in the graph? I haven't marked your nice answer as "accepted" yet only because I won't close it: there remains a small hope that Question 2 still has an affirmative answer. – Stasys Jan 18 '13 at 11:35
  • @David: Can it be (I guess - yes) that an analogue of Erdos-Gallai result (mentioned in my edit above) holds also for transitive tournaments T_n instead of complete undirected graphs K_n? That is, every pure k-cut of T_n must have all but about kn edges of T_n? For this, we only need to ensure that every DAG without a k-path must have an inner vertex of degree at most about k; this seems to hold. If so, then the answer to my (relaxed) Question 2 would be also NO (for, say, k=n^{1/2}), because then M would already be large, about n^2. – Stasys Jan 19 '13 at 18:43
  • I'm not sure what you mean by the degree bound. If you mean outdegree, then every DAG has a vertex other than its source s and sink t with outdegree at most one: take the vertex next to t in a topological ordering. On the other hand, if you mean total degree, then it's easy to find DAGs with no k-path in which all nodes have big total degree: arrange the nodes into k-1 layers, with s in the first layer, t in the last layer, and n/(k-3) nodes in every other layer, and connect all pairs of nodes that are in different layers from each other. – David Eppstein Jan 20 '13 at 00:51
  • Right, k-path-freeness of a digraph only implies outdeg(x)+indeg(y) < 2k-3 for some nonedge (x,y). But your last example ("complete" layered DAG) shows that, in order to destroy all paths (not just s-t paths) in T_n (transitive tournament), it is enough to remove about f(n,k):=k \binom{n/k}{2} = n^2/2k - n/2 edges, far fewer than in K_n (where we need to remove (n-k)n/2 edges). Thus, M \leq f(n,k) in Question 2, meaning that T_n is not an immediate counterexample for this question. This is good news. Interestingly, your answer to Question 1 also implies that M\geq f(n,k). – Stasys Jan 20 '13 at 16:53