- cc.complexity-theory graph-theory circuit-complexity directed-acyclic-graph
- Updated Sun, 29 May 2022 12:04:14 GMT

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:

- 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$. - 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 exist^{1} 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$.

^{1}The 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}$.

[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".

External links referenced by this document:

- https://cstheory.stackexchange.com/a/16123/5788
- https://en.wikipedia.org/wiki/Topological_sorting
- https://en.wikipedia.org/wiki/Tournament_(graph_theory)
- http://ieeexplore.ieee.org/xpl/login.jsp?tp=&arnumber=4568095&url=http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=4568095
- http://www.sciencedirect.com/science/article/pii/0016003256905592
- http://www.sciencedirect.com/science/article/pii/030439758290113X
- http://www.thi.informatik.uni-frankfurt.de/~jukna/boolean/Markov-threshold.pdf
- http://www.thi.informatik.uni-frankfurt.de/~jukna/drafts/mincut.pdf
- http://www.thi.informatik.uni-frankfurt.de/~jukna/drafts/old-answer.html

Local articles referenced by this article: