# Transitive reduction with vertex additions?

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?