Minimum Equivalent Digraph

Input

Directed graph $G = (V,A)$, positive integer $K \leq |A|$.

Question

IS there a subset $A' \subseteq A$ with $|A'| \leq K$ such that, for every ordered pair of vertices $u, v \in V$, the graph $G' = (V, A')$ contains a directed path from $u$ to $v$ if and only if $G$ does?

Classes

• NP-complete

Comments

Corresponding problem in which $A' \subseteq V \times V$ instead of $A' \subseteq A$ (called [problem:transitive-reduction]) can be solved in polynomial time, e.g. see (Aho et al., 1972).

Proofs

NP-complete

Transformation from Directed Hamiltonian Circuit for strongly connected graphs (Sahni, 1974).

Reducible from

• Directed Hamiltonian Circuit

References

• Aho, A. V., Garey, M. R., & Ullman, J. D. (1972). The Transitive Reduction of a Directed Graph. SIAM Journal on Computing, 1(2), 131–137. https://doi.org/10.1137/0201008
• Sahni, S. (1974). Computationally Related Problems. SIAM Journal on Computing, 3(4), 262–279. https://doi.org/10.1137/0203021