Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

On exact complexity of subgraph homeomorphism

Lingas, Andrzej LU and Wahlén, Martin LU (2007) 4th International Conference, TAMC 2007 4484. p.256-261
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... (More)
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. (Less)
Please use this url to cite or link to this publication:
author
and
organization
publishing date
type
Chapter in Book/Report/Conference proceeding
publication status
published
subject
host publication
Theory and Applications of Models of Computation / Lecture Notes in Computer Science
editor
Cai, Jin-yi ; Cooper, Barry and Zhu, Hong
volume
4484
pages
256 - 261
publisher
Springer
conference name
4th International Conference, TAMC 2007
conference location
Shanghai, China
conference dates
2007-05-22 - 2007-05-25
external identifiers
  • wos:000246671900023
  • scopus:35448973245
ISBN
978-3-540-72503-9
DOI
10.1007/978-3-540-72504-6_23
project
VR 2005-4085
language
English
LU publication?
yes
id
49ea2528-7f32-47e1-995e-74218864f3d9 (old id 587893)
alternative location
http://www.springerlink.com/content/9853653753736560/fulltext.pdf
date added to LUP
2016-04-04 11:21:07
date last changed
2022-03-23 17:27:17
@inproceedings{49ea2528-7f32-47e1-995e-74218864f3d9,
  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.<br/><br>
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.}},
  author       = {{Lingas, Andrzej and Wahlén, Martin}},
  booktitle    = {{Theory and Applications of Models of Computation / Lecture Notes in Computer Science}},
  editor       = {{Cai, Jin-yi and Cooper, Barry and Zhu, Hong}},
  isbn         = {{978-3-540-72503-9}},
  language     = {{eng}},
  pages        = {{256--261}},
  publisher    = {{Springer}},
  title        = {{On exact complexity of subgraph homeomorphism}},
  url          = {{http://dx.doi.org/10.1007/978-3-540-72504-6_23}},
  doi          = {{10.1007/978-3-540-72504-6_23}},
  volume       = {{4484}},
  year         = {{2007}},
}