On exact complexity of subgraph homeomorphism
Author
Editor
- Jin-yi Cai
- Barry Cooper
- Hong Zhu
Summary, in English
The subgraph homeomorphism problem is to decide whether 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 graph. The restriction of subgraph homeomorphism where an injective mapping of the vertices of the pattern graph into vertices of the host graph is already given is termed fixed-vertex subgraph homeomorphism.
We show that fixed-vertex subgraph homeomorphism for a pattern graph on p vertices and a host graph on n vertices can be solved in time O(2n − pnO(1)) or in time O(3n − pn6) and polynomial space. In effect, we obtain new non-trivial upper time-bounds on the exact complexity of the problem of finding k vertex-disjoint paths and general subgraph homeomorphism.
We show that fixed-vertex subgraph homeomorphism for a pattern graph on p vertices and a host graph on n vertices can be solved in time O(2n − pnO(1)) or in time O(3n − pn6) and polynomial space. In effect, we obtain new non-trivial upper time-bounds on the exact complexity of the problem of finding k vertex-disjoint paths and general subgraph homeomorphism.
Department/s
- Computer Science
Publishing year
2007
Language
English
Pages
256-261
Publication/Series
Theory and Applications of Models of Computation / Lecture Notes in Computer Science
Volume
4484
Links
Document type
Conference paper
Publisher
Springer
Topic
- Computer Science
Conference name
4th International Conference, TAMC 2007
Conference date
2007-05-22 - 2007-05-25
Conference place
Shanghai, China
Status
Published
Project
- VR 2005-4085
ISBN/ISSN/Other
- ISBN: 978-3-540-72503-9