0
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ Could you explain what an "equivalent graph" is? $\endgroup$ – David Richerby Jan 11 '18 at 15:36
0
$\begingroup$

This problem (or more precisely, its decision version) lies in NP, as a small enough equivalent digraph would give an NP-certificate. What remains is to show that this problem is NP-hard.

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.