• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - No thumbnail

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érence
External document link
http://arxiv.org/abs/1412.1261v1
Date
2015
Conference title
25th International Workshop on Combinatorial Algorithms, IWOCA 2014
Conference date
2014-10
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
Book author
Kratochvil, Jan; Miller, Mirka; Dalibor, Froncek
Publisher
Springer International Publishing
Published in
Berlin
ISBN
978-3-319-19314-4
Pages
1-12
Publication identifier
10.1007/978-3-319-19315-1_1
Metadata
Show full item record
Author(s)
Abu-Khzam, Faisal N.

Bonnet, Édouard cc
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Sikora, Florian cc
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 Subgraph

Related items

Showing items related by title and author.

  • Thumbnail
    On the complexity of various parameterizations of common induced subgraph isomorphism 
    Abu-Khzam, Faisal N.; Bonnet, Édouard; Sikora, Florian (2017) Article accepté pour publication ou publié
  • Thumbnail
    On the Complexity of QoS-Aware Service Selection Problem 
    Abu-Khzam, Faisal N.; Bazgan, Cristina; El Haddad, Joyce; Sikora, Florian (2015) Communication / Conférence
  • Thumbnail
    Complexity of Grundy Coloring and Its Variants 
    Bonnet, Édouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian (2015) Communication / Conférence
  • Thumbnail
    Complexity of Grundy coloring and its variants 
    Bonnet, Édouard; Foucaud, Florent; Kim, Eun Jung; Sikora, Florian (2018) Article accepté pour publication ou publié
  • Thumbnail
    The Graph Motif problem parameterized by the structure of the input graph 
    Bonnet, Édouard; Sikora, Florian (2017) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo