In the article:

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



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.


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.