# Finding a minimum equivalent graph of a digraph

It is said that this problem is NP-complete but I couldn't find the proof. Is there any paper on this problem or not?

• Could you explain what an "equivalent graph" is? – David Richerby Jan 11 '18 at 15:36

This paper shows that finding a minimum equivalent digraph is NP-hard even when restricted to digraphs with cycles of length at most $5$, via a reduction from SAT. This means that the problem in general is NP-hard and therefore also NP-complete.