Do sparse DAGs can have large min-cuts?

2013-01-21T20:39:11Z

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 (transitive tournament) on $n$ vertices; hence $e(K_n)=e(T_n)=\tbinom{n}{2}$.

A classical result of Erdő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). $$ Proof: 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 < 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.

The other direction $c_k(T_n)\geq k\tbinom{n/k}{2}$ was essentially shown by David Eppstein in this answer: 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 longest-path 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.

Motivated by this (remarkable) difference between $c_k(K_n)$ and $c_k(T_n)$, here is my

Question: Does $c_k(G)$ is at most "about" $e(G)/k$ for every acyclic digraph $G$?

By "about" I mean "times some absolute constant or times some slowly growing function in $n$".

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 Menger’s theorem (attributed to Robacker): in any directed graph, the minimum length $t$ of a path is equal to the maximum number of edge-disjoint cuts. (The proof is elementary, see e.g. here.)

Besides being natural in itself, an affirmative answer to my question would have some interesting consequences in boolean function complexity (see this post and references herein).

Answer by Stasys for Do sparse DAGs can have large min-cuts?

2013-01-27T20:17:50Z

I just realized that the answer to my question is (as suspected) NO. Namely, in this 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 < 1$ and $k=n^{\epsilon}$, we have that $c_k(G)\geq \alpha\cdot e(G)$, where $\alpha=\alpha(\epsilon)$ is a constant 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 Kraft inequality, 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).

The graph $G$ is constructed as follows. 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.

This example also shows the optimality of depth-reductions for DAGs proved by Erdős, Graham and Szemerédi, and generalized by Valiant to the following important fact:

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$.

Do sparse DAGs can have large min-cuts? - MathOverflow

Do sparse DAGs can have large min-cuts?

Answer by Stasys for Do sparse DAGs can have large min-cuts?