Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

Maximum common induced subgraph parameterized by vertex cover

Abu-Khzam, Faisal N. (2014). Maximum common induced subgraph parameterized by vertex cover. Information Processing Letters,114(3):99-103.

Document type: Journal Article
Citation counts:
Google Scholar Search Google Scholar

IRMA ID 84373604xPUB72
Title Maximum common induced subgraph parameterized by vertex cover
Author Abu-Khzam, Faisal N.
Journal Name Information Processing Letters
Publication Date 2014
Volume Number 114
Issue Number 3
ISSN 0020-0190   (check CDU catalogue open catalogue search in new window)
Scopus ID 2-s2.0-84890087284
Start Page 99
End Page 103
Total Pages 5
Place of Publication Netherlands
Publisher Elsevier BV
HERDC Category C1 - Journal Article (DIISR)
Abstract The Maximum Common Induced Subgraph problem (MCIS ) takes a pair of graphs as input and asks for a graph of maximum order that is isomorphic to an induced subgraph of each of the input graphs. The problem is NPNP-hard in general, and remains so on many graph classes including graphs of bounded treewidth. In the framework of parameterized complexity, the latter assertion means that MCIS is W[1]W[1]-hard when parameterized by the treewidths of input graphs.

A classical graph parameter that has been used recently in many parameterization problems is Vertex Cover. In this paper we prove constructively that MCIS is fixed-parameter tractable when parameterized by the vertex cover numbers of the input graphs. Our algorithm is also an improved exact algorithm for the problem on instances where the minimum vertex cover is small compared to the order of input graphs.
Keywords Graph algorithms
Vertex cover
Common subgraph isomorphism
Maximum common subgraph
Fixed-parameter tractability
DOI http://dx.doi.org/10.1016/j.ipl.2013.11.007   (check subscription with CDU E-Gateway service for CDU Staff and Students  check subscription with CDU E-Gateway in new window)
 
Versions
Version Filter Type
Access Statistics: 157 Abstract Views  -  Detailed Statistics
Created: Wed, 19 Aug 2015, 12:25:34 CST