The directed subgraph homeomorphism problem

The set of pattern graphs for which the fixed directed subgraph homeomorphism problem is NP-complete is characterized. A polynomial time algorithm is given for the remaining cases. The restricted problem where the input graph is a directed acyclic graph is in polynomial time for all pattern graphs and an algorithm is given.

Authors

• Steven Fortune
• John Hopcroft
• James Wyllie

Keywords

No keywords are indexed for this paper.