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?