Transitive reduction with vertex additions?

Question

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?

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