• français
    • English
  • English 
    • français
    • English
  • Login
JavaScript is disabled for your browser. Some features of this site may not work without it.
BIRD Home

Browse

This CollectionBy Issue DateAuthorsTitlesSubjectsJournals BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesSubjectsJournals

My Account

Login

Statistics

View Usage Statistics

On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism

Thumbnail
Date
2015
Link to item file
http://arxiv.org/abs/1412.1261v1
Dewey
Recherche opérationnelle
Sujet
Maximum Common Induced Subgraph
DOI
http://dx.doi.org/10.1007/978-3-319-19315-1_1
Conference name
25th International Workshop on Combinatorial Algorithms, IWOCA 2014
Conference date
10-2014
Conference city
Duluth
Conference country
United States
Book title
Combinatorial Algorithms. 25th International Workshop, IWOCA 2014, Duluth, MN, USA, October 15-17, 2014, Revised Selected Papers
Author
Kratochvil, Jan; Miller, Mirka; Dalibor, Froncek
Publisher
Springer International Publishing
Publisher city
Berlin
Year
2015
ISBN
978-3-319-19314-4
Book URL
10.1007/978-3-319-19315-1
URI
https://basepub.dauphine.fr/handle/123456789/15781
Collections
  • LAMSADE : Publications
Metadata
Show full item record
Author
Abu-Khzam, Faisal N.
status unknown
Bonnet, Édouard
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sikora, Florian
989 Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Type
Communication / Conférence
Item number of pages
1-12
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.

  • Accueil Bibliothèque
  • Site de l'Université Paris-Dauphine
  • Contact
SCD Paris Dauphine - Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16

 Content on this site is licensed under a Creative Commons 2.0 France (CC BY-NC-ND 2.0) license.