The transitive reduction of a (finite) directed graph is a graph with the same vertex set and reachability relation and a minimum number of edges. However, what if vertex additions are allowed? In some cases, the addition of vertices can considerably reduce the number of edges required. For example, a complete bipartite digraph $K_{a,b}$ has $a + b$ veritices and $ab$ edges, but the addition of a single vertex in the middle results in a digraph with the same reachability relation that has $a + b + 1$ vertices and only $a + b$ edges.

More formally, given a directed graph $G = (V, E)$, the challenge is to find $G' = (V', E')$ and injective function $f: V \rightarrow V'$ such that $f(b)$ is reachable from $f(a)$ in $G'$ if and only if $b$ is reachable from $a$ in $G$ and such that $|E'|$ is minimized.

Are there any known results or algorithms related to this problem?


1 Answer 1


I don't think that any such "small" graph can exist in general.

Let $n$ be a multiple of $4$ and pick your favorite binary string $s = \langle s_0, \dots, s_{\ell-1} \rangle$ of length $ \ell = \frac{n^2}{4}$.

Build a directed bipartite graph $G_s = (A \cup B, E)$ on $n$ vertices where $A = \{a_0, \dots, a_{\frac{n}{2}-1}\}$ and $B = \{b_0, \dots, b_{\frac{n}{2}-1}\}$. $E$ contains the edge $(a_i,b_j) \in A \times B$ iff $s_{\frac{in}{2} + j}$ is $1$.

Let $G'_s$ be the smallest graph obtainable from $G_s$ that preserves connectivity relations. Notice that, from $G'_s$, it is possible to recover the whole string $s$.

There are $2^\ell$ choices for $s$, which means that, for at least one graph $G_s$, the minimum number of bits needed to encode $G'_s$ must be at least $\ell = \Omega(n^2)$.

Notice that $O(m \log n)$ bits suffice to encode any graph with $m$ edges and $n$ vertices. This means that $G'_s = (V', E')$ must be such that $|E'| \cdot \log |V'| \cdot \log n = \Omega(n^2)$.

  • 1
    $\begingroup$ I don't think the part about having exactly l/2 ones is necessary. You can just take all l bit strings, which simplifies the argument slightly. Anyway, thanks for this. A bit disappointing to find out that you can't meaningfully simplify graphs this way, but it does save a lot of useless effort trying to find a solution. I can't believe I didn't think about the entropy of the reachability relation before. $\endgroup$
    – Antimony
    Mar 29, 2020 at 22:05
  • 1
    $\begingroup$ This proves that there exist graphs where we can't achieve any reduction (or not much reduction). It's still interesting to ask whether there exists an algorithm that outputs the smallest reduction possible. In some cases (such as the graphs you outlined) the output might be the same as the input, if that is the smallest possible. $\endgroup$
    – D.W.
    Mar 29, 2020 at 22:46
  • $\begingroup$ It doesn't completely answer the question. It just shows that, in the worst case, there are dense graphs that can't be sparsified while preserving connectivity relations. Often times, for sparsification problems (for example graph spanners) one cares about the worst possible asymptotic size of the output graph as a function of the size of the input graph. $\endgroup$
    – Steven
    Mar 29, 2020 at 22:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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