TY - GEN

T1 - On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism

AU - Abu Khzam, Faisal

AU - Bonnet, Edouard

AU - Sikora, Florian

PY - 2014

Y1 - 2014

N2 - 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 xed-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 xedparameter 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 ve and, unless P = NP, they do not to 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.

AB - 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 xed-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 xedparameter 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 ve and, unless P = NP, they do not to 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.

U2 - 10.1007/978-3-319-19315-1_1

DO - 10.1007/978-3-319-19315-1_1

M3 - Conference Paper published in Proceedings

SN - 978-3-319-19314-4

T3 - Lecture Notes in Computer Science book series

SP - 1

EP - 12

BT - Combinatorial Algorithms

PB - Springer

CY - Duluth, USA

T2 - International Workshop on Combinatorial Algorithms (IWOCA) 2014 25th

Y2 - 15 October 2014 through 17 October 2014

ER -