Anzeige
Erschienen in:
2015 | OriginalPaper | Buchkapitel
On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism
verfasst von : Faisal N. Abu-Khzam, Édouard Bonnet, Florian Sikora
Erschienen in: Combinatorial Algorithms
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
Maximum Common Induced Subgraph (henceforth MCIS) is among the most studied classical \({\mathsf {NP}}\)-hard problems. MCIS remains \({\mathsf {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 \({\mathsf {NP}}\subseteq \mathsf {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 \({\mathsf {W[1]}}\)-complete on bipartite graphs and graphs of girth five and, unless \({\mathsf {P}}= {\mathsf {NP}}\), they do not belong to the class \({\mathsf {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.