Title: Disjoint directed and undirected paths and cycles in digraphs
Abstract: We show that the following problem is NP-complete: Given a digraph D and distinct vertices s,t of D, decide whether the underlying graph of D contains two internally disjoint (s,t)-paths P and Q such that P is a directed (s,t)-path in D. Using this result we characterize those mixed linkage problems which are polynomially solvable (assuming P≠NP). This complements the classical dichotomy by Fortune, Hopcroft, and Wyllie classifying those directed linkage problems that are polynomially solvable. We furthermore show that, contrary to the case of directed linkages in digraphs, the mixed problem remains NP-complete for acyclic digraphs.
Publication Year: 2009
Publication Date: 2009-11-01
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
Cited By Count: 13
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot