2
$\begingroup$

In the article:

S. Fortune, J. Hopcroft, J. Wyllie, The directed subgraphs homeomorphism problem, Theoret. Comput. Sci. 10 (1980) 111–121.

link:

https://www.sciencedirect.com/science/article/pii/0304397580900092

It is proved that the 2-DIRECTED DISJOINT PATHS PROBLEM is NP-complete in general digraphs. The proof is pretty concise, but I have some difficulties with figuring the correctness of the given reduction from 3-SAT, mostly due to the old-fashion writing and omitted justification of details.

Does anyone here know a resource, say a textbook, in which a more comprehensible version of this proof (or maybe an alternative one) is presented?

Thanks in advance.

$\endgroup$

Your Answer

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

Browse other questions tagged or ask your own question.