On the complexity of various parameterizations of common induced subgraph isomorphism

LAUR Repository

Show simple item record

dc.contributor.author Abu-Khzam, Faisal N.
dc.contributor.author Bonnet, Edouard
dc.contributor.author Sikora, Florian
dc.date.accessioned 2017-03-16T11:01:33Z
dc.date.available 2017-03-16T11:01:33Z
dc.date.issued 2017-03-16
dc.identifier.uri http://hdl.handle.net/10725/5376
dc.description.abstract Maximum Common Induced Subgraph (henceforth MCIS) is among the most studied classical NPNP -hard problems. MCIS remains NPNP -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/polyNP⊆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]W[1] -complete on bipartite graphs and graphs of girth five and, unless P=NPP=NP , they do not belong to the class XPXP 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. en_US
dc.language.iso en en_US
dc.publisher Springer en_US
dc.title On the complexity of various parameterizations of common induced subgraph isomorphism en_US
dc.type Conference Paper / Proceeding en_US
dc.author.school SAS en_US
dc.author.idnumber 200302941 en_US
dc.author.department Computer Science and Mathematics en_US
dc.description.embargo N/A en_US
dc.identifier.doi http://dx.doi.org/10.1007/978-3-319-19315-1_1 en_US
dc.identifier.ctation Abu-Khzam, F. N., Bonnet, É., & Sikora, F. (2014, October). On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism. In International Workshop on Combinatorial Algorithms (pp. 1-12). Springer International Publishing. en_US
dc.author.email faisal.abukhzam@lau.edu.lb en_US
dc.conference.pages 1-12 en_US
dc.conference.title International Workshop on Combinatorial Algorithms en_US
dc.identifier.tou http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php en_US
dc.identifier.url https://link.springer.com/chapter/10.1007/978-3-319-19315-1_1 en_US
dc.publication.date 2014 en_US
dc.author.affiliation Lebanese American University en_US
dc.title.volume Combinatorial Algorithms en_US

Files in this item

This item appears in the following Collection(s)

Show simple item record

Search LAUR

Advanced Search


My Account