On exact complexity of subgraph homeomorphism

Research output: Chapter in Book/Report/Conference proceedingPaper in conference proceeding

Abstract

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.

Details

Authors
Research areas and keywords

Subject classification (UKÄ) – MANDATORY

  • Computer Science
Original languageEnglish
Title of host publicationTheory and Applications of Models of Computation / Lecture Notes in Computer Science
EditorsJin-yi Cai, Barry Cooper, Hong Zhu
PublisherSpringer
Pages256-261
Volume4484
ISBN (Print)978-3-540-72503-9
Publication statusPublished - 2007
Publication categoryResearch
Peer-reviewedYes
Event4th International Conference, TAMC 2007 - Shanghai, China
Duration: 2007 May 222007 May 25

Publication series

Name
Volume4484

Conference

Conference4th International Conference, TAMC 2007
CountryChina
CityShanghai
Period2007/05/222007/05/25