Return to Question

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](http://www.renyi.hu/~p_erdos/1959-10.pdf) 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](http://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have): 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](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html) (see [this](http://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have) post and references herein).

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](http://www.renyi.hu/~p_erdos/1959-10.pdf) 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](https://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have): 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](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html) (see [this](https://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have) post and references herein).

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](http://www.renyi.hu/~p_erdos/1959-10.pdf) 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 Epppstein in this [answer](http://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have): 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](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html) (see [this](http://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have) post and references herein).

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](http://www.renyi.hu/~p_erdos/1959-10.pdf) 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](http://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have): 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](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html) (see [this](http://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have) post and references herein).

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](http://www.renyi.hu/~p_erdos/1959-10.pdf) 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 Epppstein in this [answer](http://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have): 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$". Also, here we may assume that $c_k(G)$ is the smallest number of edges that must be removed in order to destroy all paths of length $\geq k+1$ going from a source (fanin $0$) node to a target (fanout $0$) node, not necessarily all possible paths of this length.

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](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html) (see [this](http://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have) post and references herein).

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](http://www.renyi.hu/~p_erdos/1959-10.pdf) 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 Epppstein in this [answer](http://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have): 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](http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/index.html) (see [this](http://cstheory.stackexchange.com/questions/16104/how-many-disjoint-edge-cuts-a-dag-must-have) post and references herein).