The set of pattern graphs for which the 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.
Cited By
- Fouquet Y, Nace D, Pióro M, Poss M and Żotkiewicz M (2015). Generalized elastic flow rerouting scheme, Networks, 66:4, (267-281), Online publication date: 1-Dec-2015.
- Bansal N, Friggstad Z, Khandekar R and Salavatipour M (2014). A logarithmic approximation for unsplittable flow on line graphs, ACM Transactions on Algorithms, 10:1, (1-15), Online publication date: 1-Jan-2014.
- Kobayashi Y and Yoshida Y Algorithms for finding a maximum non-k-linked graph Proceedings of the 19th European conference on Algorithms, (131-142)
- Naves G, Sonnerat N and Vetta A Maximum flows on disjoint paths Proceedings of the 13th international conference on Approximation, and 14 the International conference on Randomization, and combinatorial optimization: algorithms and techniques, (326-337)
- Dressler D and Strehler M Capacitated confluent flows Proceedings of the 7th international conference on Algorithms and Complexity, (347-358)
- Gu Y and Wu Q Optimizing distributed computing workflows in heterogeneous network environments Proceedings of the 11th international conference on Distributed computing and networking, (142-154)
- Moreira N and Reis R (2019). Series-Parallel Automata and Short Regular Expressions, Fundamenta Informaticae, 91:3-4, (611-629), Online publication date: 1-Aug-2009.
- Moreira N and Reis R (2019). Series-Parallel Automata and Short Regular Expressions, Fundamenta Informaticae, 91:3-4, (611-629), Online publication date: 1-Aug-2009.
- Kobayashi Y and Sommer C On Shortest Disjoint Paths in Planar Graphs Proceedings of the 20th International Symposium on Algorithms and Computation, (293-302)
- Kawarabayashi K and Kobayashi Y The induced disjoint paths problem Proceedings of the 13th international conference on Integer programming and combinatorial optimization, (47-61)
- Kirousis L and Kolaitis P (2019). The complexity of minimal satisfiability problems, Information and Computation, 187:1, (20-39), Online publication date: 25-Nov-2003.
- Afrati F (2019). Bounded Arity Datalog(≠) Queries on Graphs, Journal of Computer and System Sciences, 55:2, (210-228), Online publication date: 1-Oct-1997.
- Cypher A An approach to the k paths problem Proceedings of the twelfth annual ACM symposium on Theory of computing, (211-217)
Recommendations
An exact algorithm for subgraph homeomorphism
The subgraph homeomorphism problem is to decide if there is an injective mapping of the vertices of a pattern graph into vertices of a host graph so that the edges of the pattern graph can be mapped into (internally) vertex-disjoint paths in the host ...
Approximating the maximum clique minor and some subgraph homeomorphism problems
We consider the ''minor'' and ''homeomorphic'' analogues of the maximum clique problem, i.e., the problems of determining the largest h such that the input graph (on n vertices) has a minor isomorphic to K"h or a subgraph homeomorphic to K"h, ...
Parameterized complexity of the induced subgraph problem in directed graphs
In this Letter, we consider the parameterized complexity of the following problem: Given a hereditary property P on digraphs, an input digraph D and a positive integer k, does D have an induced subdigraph on k vertices with property P? We completely ...