Do sparse DAGs can have large min-cuts? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-24T20:34:55Z http://mathoverflow.net/feeds/question/119511 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/119511/do-sparse-dags-can-have-large-min-cuts Do sparse DAGs can have large min-cuts? Stasys 2013-01-21T20:39:11Z 2013-01-28T15:33:44Z <p>For a graph $G$, let $e(G)$ denote the number of its edges, and $c_k(G)$ the smallest number of edges that must be removed in order to destroy all paths of length $\geq k+1$. Note that $c_1(G)\geq c_2(G)\geq \ldots\geq c_k(G)\geq \ldots$. Let $K_n$ be a complete graph, and $T_n$ a complete acyclic digraph (<a href="http://en.wikipedia.org/wiki/Tournament_%28graph_theory%29" rel="nofollow">transitive tournament</a>) on $n$ vertices; hence $e(K_n)=e(T_n)=\tbinom{n}{2}$. <p> A classical <a href="http://www.renyi.hu/~p_erdos/1959-10.pdf" rel="nofollow">result</a> of Erd&#337;s and Gallai states that $$c_k(K_n)=e(K_n)-\frac{kn}{2}.$$ In contrast, for the directed acyclic analogue $T_n$ of $K_n$, we have $$c_k(T_n)= k\binom{n/k}{2}=\frac{e(T_n)}{k}+\frac{n}{2}\Big(1-\frac{1}{k}\Big).$$ <b>Proof:</b> To show $c_k(T_n)\leq k\tbinom{n/k}{2}$, take a topological order of vertices of $T_n$: vertices $i$ and $j$ are adjacent iff $i &lt; j$. Split the vertices into $k$ consecutive intervals of length $n/k$. If we remove all edges whose both endpoints lie in the same interval, then we destroy all paths of length $\geq k+1$. Since only $k\tbinom{n/k}{2}$ edges were removed, we are done. <p> The other direction $c_k(T_n)\geq k\tbinom{n/k}{2}$ was essentially shown by David Eppstein in this <a href="http://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have" rel="nofollow">answer</a>: Let $C$ be a set of edges whose removal destroys all paths of length $≥k+1$ in $T_n$. Split the vertices into $t\leq k$ layers, where the $i$-th layer contains all vertices $u$ such that the length of a longest path to $u$ in $T_n\setminus C$ has length $i$. Since each layer is a layer of the <i>longest-path</i> layering, it is independent in $T_n\setminus C$, and therefore complete in $C$. Thus, if $n_i$ is the number of vertices in the $i$-th layer, then the total number of edges in $C$ is at least $\sum_{i=1}^t\tbinom{n_i}{2}\geq t\tbinom{n/t}{2}\geq k\tbinom{n/k}{2}$, as desired. Q.E.D. <p> Motivated by this (remarkable) difference between $c_k(K_n)$ and $c_k(T_n)$, here is my </p> <blockquote> <b>Question:</b> Does $c_k(G)$ is at most "about" $e(G)/k$ for <i>every</i> acyclic digraph $G$? </blockquote> <p>By "about" I mean "times some absolute constant or times some slowly growing function in $n$". <p></p> <p>Note that the problem is only to get rid with graphs having also short paths (shorter than $k$), because $c_1(G)\leq e(G)/t$ holds for any (not necessarily acyclic) digraph $G$, where $t$ is the length of a shortest source-to-target path. This is a direct consequence of a dual to <a href="http://en.wikipedia.org/wiki/Menger%27s_theorem" rel="nofollow">Menger’s theorem</a> (attributed to Robacker): in any directed graph, the <i>minimum</i> length $t$ of a path is equal to the <i>maximum</i> number of edge-disjoint cuts. (The proof is elementary, see e.g. <a href="http://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have" rel="nofollow">here</a>.) <p> Besides being natural in itself, an affirmative answer to my question would have some interesting consequences in <a href="http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html" rel="nofollow">boolean function complexity</a> (see <a href="http://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have" rel="nofollow">this</a> post and references herein). </p> http://mathoverflow.net/questions/119511/do-sparse-dags-can-have-large-min-cuts/120049#120049 Answer by Stasys for Do sparse DAGs can have large min-cuts? Stasys 2013-01-27T20:17:50Z 2013-01-27T20:25:02Z <p>I just realized that the answer to my question is (as suspected) NO. Namely, in <a href="http://www.sciencedirect.com/science/article/pii/030439758290113X" rel="nofollow">this</a> paper, Georg Schnitger constructed a directed acyclic graph $G$ with $n$ vertices, and $e(G)\approx n\log n$ edges such that, for every $0\leq \epsilon &lt; 1$ and $k=n^{\epsilon}$, we have that $c_k(G)\geq \alpha\cdot e(G)$, where $\alpha=\alpha(\epsilon)$ is a <i>constant</i> depending only on $\epsilon$. This is much larger than the "desired" upper bound $c_k(G)\leq e(G)/k$. Actually, I think that using the <a href="http://en.wikipedia.org/wiki/Kraft%27s_inequality" rel="nofollow">Kraft inequality</a>, one can show that $c_k(G)=\Omega(n\log(n/k))$ holds for every $k$: show that at least $m\log m$ edges must be removed in order to disconnect any given subset of $m$ leaves, and use the argument of the proof above (haven't verified the details yet). <p> The graph $G$ is constructed as follows. <img src="http://www.thi.informatik.uni-frankfurt.de/~jukna/georg.jpg" alt="alt text"> Take a complete binary tree of depth $t$; hence, we have $n=2^{t+1}-1$ vertices. Remove all edges. Connect each vertex with all leaves, which were previously its descendants. Direct the new edges in the following way: the vertex receives edges from his left leaves and sends edges to his right leaves. <p> This example also shows the optimality of depth-reductions for DAGs proved by <a href="http://www.renyi.hu/~p_erdos/1976-26.pdf" rel="nofollow">Erd&#337;s, Graham and Szemer&#233;di</a>, and generalized by <a href="http://link.springer.com/chapter/10.1007%2F3-540-08353-7_135?LI=true" rel="nofollow">Valiant</a> to the following important fact:</p> <blockquote> In a DAG with $m$ edges and depth (maximum length of a path) $d$, it is enough to take out $mr/\log d$ edges to reduce the depth to $d/2^r$. </blockquote>