Charles Darwin University

CDU eSpace
Institutional Repository

 
CDU Staff and Student only
 

On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism

Abu-Khzam, Faisal N., Bonnet, Edouard and Sikora, Florian (2014). On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism. In: 25th International Workshop, IWOCA 2014, Duluth, Minnesota, USA, 15-17 October 2014.

Document type: Conference Paper
Citation counts: Google Scholar Search Google Scholar

IRMA ID 84373604xPUB74
Author Abu-Khzam, Faisal N.
Bonnet, Edouard
Sikora, Florian
Title On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism
Conference Name 25th International Workshop, IWOCA 2014
Conference Location Duluth, Minnesota, USA
Conference Dates 15-17 October 2014
Conference Publication Title Combinatorial Algorithmus - Volume 8986 of the series Lecture otes in Computer Science
Publisher Springer
Publication Year 2014
Volume Number 8986
ISBN 978-3-319-19314-4   (check CDU catalogue open catalogue search in new window)
ISSN 302-9743   (check CDU catalogue open catalogue search in new window)
Start Page 1
End Page 12
Total Pages 12
HERDC Category E1 - Conference Publication (DIISR)
Abstract Maximum Common Induced Subgraph (henceforth MCIS) is among the most studied classical NP-hard problems. MCIS remains NP-hard on many graph classes including bipartite graphs, planar graphs and k-trees. Little is known, however, about the parameterized complexity of the problem. When parameterized by the vertex cover number of the input graphs, the problem was recently shown to be fixed-parameter tractable. Capitalizing on this result, we show that the problem does not have a polynomial kernel when parameterized by vertex cover unless NP⊆coNP/poly. We also show that Maximum Common Connected Induced Subgraph (MCCIS), which is a variant where the solution must be connected, is also fixed-parameter tractable when parameterized by the vertex cover number of input graphs. Both problems are shown to be W[1]-complete on bipartite graphs and graphs of girth five and, unless P=NP, they do not belong to the class XP when parameterized by a bound on the size of the minimum feedback vertex sets of the input graphs, that is solving them in polynomial time is very unlikely when this parameter is a constant.
Description for Link Link to publisher's version
URL http://link.springer.com/chapter/10.1007%2F978-3-319-19315-1_1
 
Versions
Version Filter Type
Access Statistics: 16 Abstract Views  -  Detailed Statistics
Created: Wed, 19 Aug 2015, 16:41:10 CST