On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism
Abu-Khzam, Faisal N.; Bonnet, Édouard; Sikora, Florian (2015), On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism, in Kratochvil, Jan; Miller, Mirka; Dalibor, Froncek, Combinatorial Algorithms. 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected Papers, Springer International Publishing : Berlin, p. 1-12. 10.1007/978-3-319-19315-1_1
Type
Communication / ConférenceExternal document link
http://arxiv.org/abs/1412.1261v1Date
2015Conference title
25th International Workshop on Combinatorial Algorithms, IWOCA 2014Conference date
2014-10Conference city
DuluthConference country
United StatesBook title
Combinatorial Algorithms. 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected PapersBook author
Kratochvil, Jan; Miller, Mirka; Dalibor, FroncekPublisher
Springer International Publishing
Published in
Berlin
ISBN
978-3-319-19314-4
Pages
1-12
Publication identifier
Metadata
Show full item recordAuthor(s)
Abu-Khzam, Faisal N.Bonnet, Édouard

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sikora, Florian

Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Abstract (EN)
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.Subjects / Keywords
Maximum Common Induced SubgraphRelated items
Showing items related by title and author.
-
Abu-Khzam, Faisal N.; Bonnet, Édouard; Sikora, Florian (2017) Article accepté pour publication ou publié
-
Abu-Khzam, Faisal N.; Bazgan, Cristina; El Haddad, Joyce; Sikora, Florian (2015) Communication / Conférence
-
Bonnet, Édouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian (2015) Communication / Conférence
-
Bonnet, Édouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian (2018) Article accepté pour publication ou publié
-
Bonnet, Édouard; Sikora, Florian (2017) Article accepté pour publication ou publié