We consider DAGs (directed acyclic graphs) with one source node $s$ and one target node $t$; parallel edges joining the same pair of vertices are allowed. A $k$-cut is a set of edges whose removal destroys all $s$-$t$ paths longer than $k$; shorter $s$-$t$ paths as well as long "inner" paths (those not between $s$ and $t$) may survive!

Question: Is it enough to remove at most about a $1/k$ portion of edges from a DAG in order to destroy all $s$-$t$ paths longer than $k$?

That is, if $e(G)$ denotes the total number of edges in $G$, does then every DAG $G$ have a $k$-cut with at most about $e(G)/k$ edges? Two examples:

  1. If all $s$-$t$ paths have length $> k$, then a $k$-cut with $\leq e(G)/k$ edges exists. This holds because then there must be $k$ disjoint $k$-cuts: just layer the nodes of $G$ according to their distance from the source node $s$.
  2. If $G=T_n$ is a transitive tournament (a complete DAG), then also a $k$-cut with $\leq k\binom{n/k}{2} \approx e(G)/k$ edges exists: fix a topological ordering of nodes, split the nodes into $k$ consecutive intervals of length $n/k$, and remove all edges joining the nodes of the same interval; this will destroy all $s$-$t$ paths longer than $k$.

Remark 1: A naive attempt to give a positive answer (which I also tried as first) would be to try to show that every DAG must have about $k$ disjoint $k$-cuts. Unfortunately, Example 2 shows that this attempt can badly fail: via a nice argument, David Eppstein has shown that, for $k$ about $\sqrt{n}$, the graph $T_n$ cannot have more than four disjoint $k$-cuts!

Remark 2: It is important that a $k$-cut needs only to destroy all long $s$-$t$ paths, and not necessarily all long paths. Namely, there exist1 DAGs in which every "pure" $k$-cut (avoiding edges incident to $s$ or $t$) must contain almost all edges. So, my question actually is: can the possibility to remove also edges incident with $s$ or $t$ substantially reduce the size of a $k$-cut? Most probably, the answer is negative, but I could not find a counterexample as yet.

Motivation: My question is motivated by proving lower bounds for monotone switching-and-rectifier networks. Such a network is just a DAG, some of whose edges are labeled by tests "is $x_i=1$?" (there are no tests $x_i=0$). The size of a network is the number of labeled edges. An input vector is accepted, if there is an $s$-$t$ path all whose tests are consistent with this vector. Markov has proved that, if a monotone boolean function $f$ has no minterms shorter than $l$ and no maxterms shorter than $w$, then size $l\cdot w$ is necessary. A positive answer to my question would imply that networks of size about $k\cdot w_k$ are necessary, if at least $w_k$ variables must be set to $0$ in order to destroy all minterms longer than $k$.


1The construction is given in this paper. Take a complete binary tree $T$ of depth $\log n$. Remove all edges. For every inner node $v$, draw an edge to $v$ from every leaf of the left subtree of $T_v$, and an edge from $v$ to every leaf of the right subtree of $T_v$. Thus, every two leaves of $T$ are connected by a path of length $2$ in the DAG. The DAG itself has $\sim n$ nodes and $\sim n\log n$ edges, but $\Omega(n\log n)$ edges must be removed in order to destroy all paths longer than $\sqrt{n}$.

  • Length bounded flows and cuts are closely related to the questions you ask. I recommend looking at the thesis of Baier. ftp.math.tu-berlin.de/pub/Preprints/combi/… – Chandra Chekuri Jun 25 '15 at 21:48
  • @Chandra Chekuri: thanks for the interesting link. The thesis is more about the weighted Menger's theorem for short paths/flaws. Concerning Menger for long paths, I found this paper: the min size of a k-cut is at most about k times the max number of long disjoint s-t paths. But this also doesn't seem to help. – Stasys Jun 26 '15 at 10:42
  • Sorry, I misunderstood the question. Thanks for the other reference. – Chandra Chekuri Jun 26 '15 at 16:13
up vote 8 down vote accepted

[Self answer; this is a shortened version, the old one can be found here]

We realized with Georg Schnitger that the answer to my question is strongly negative: there are DAGs (even of constant degree), where every $k$-cut must have a constant fraction of all edges, not just an about $1/k$ fraction, as in my question. (A slightly weaker result that a $1/\log k$ fraction may be necessary can be obtained by using a much simpler construction mentioned in the footnote above. A quick write-up is here)

Namely, in the paper "On depth-reduction and grates", Georg constructed a sequence of directed acyclic graphs $H_n$ of constant maximum degree $d$ on $n=m2^m$ nodes with the following property:

  • For every constant $0\leq \epsilon < 1$ there is a constant $c > 0$ such that, if any subset of at most $cn$ nodes is removed from $H_n$, the remaining graph contains a path of length at least $2^{\epsilon m}$.

Take now two new nodes $s$ and $t$, and draw an edge from $s$ to every node of $H_n$, and an edge from every node of $H_n$ to $t$. The resulting graph $G_n$ still has at most $2n+dn=O(n)$ edges.

For every constant $0\leq \epsilon < 1$, there is a constant $c ' > 0$ such that, if any subset of at most $c'n$ edges is removed from $G_n$, the remaining graph contains an $s$-$t$ path with $2^{\epsilon m}$ or more edges.

Proof: Call the nodes of $H_n$ inner nodes of $G_n$. Remove any subset of at most $c'n$ edges from $G_n$, where $c'=c/2$. After that, remove an inner node if it was incident to a removed edge. Note that at most $2c'n=cn$ inner nodes are then removed. None of the edges incident to survived nodes was removed. In particular, each survived inner node is still connected to both nodes $s$ and $t$. By the above property of $H_n$, there must remain a path of length $2^{\epsilon m}$ consisting entirely of survived inner nodes. Since the endpoints of each of these paths survived, each of them can be extended to an $s$-$t$ path in $G_n$. Q.E.D.

A consequence is sad: there does not exist any analogue of Markov's lemma for functions with many short minterms, even though the set of long minterms has some "complicated" structure: no super-linear lower bounds on the network size can be then proved using this "length times width" argument.

P.S. This "length times width" argument (when all $s$-$t$ paths are long enough) was earlier used by Moore and Shannon (1956). The only difference is that they do not allowed rectifies (unlabeled edges). So, this is, in fact, a "Moore-Shannon-Markov argument".

Your Answer

 
discard

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.

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