On the complexity of various parameterizations of common induced subgraph isomorphism
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 parameteri...
محفوظ في:
| المؤلف الرئيسي: | |
|---|---|
| مؤلفون آخرون: | , |
| التنسيق: | conferenceObject |
| منشور في: |
2017
|
| الوصول للمادة أونلاين: | http://hdl.handle.net/10725/5376 http://dx.doi.org/10.1007/978-3-319-19315-1_1 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-319-19315-1_1 |
| الوسوم: |
إضافة وسم
لا توجد وسوم, كن أول من يضع وسما على هذه التسجيلة!
|
| _version_ | 1864513465855508481 |
|---|---|
| author | Abu-Khzam, Faisal N. |
| author2 | Bonnet, Edouard Sikora, Florian |
| author2_role | author author |
| author_facet | Abu-Khzam, Faisal N. Bonnet, Edouard Sikora, Florian |
| author_role | author |
| dc.creator.none.fl_str_mv | Abu-Khzam, Faisal N. Bonnet, Edouard Sikora, Florian |
| dc.date.none.fl_str_mv | 2017-03-16T11:01:33Z 2017-03-16T11:01:33Z 2017-03-16 |
| dc.identifier.none.fl_str_mv | http://hdl.handle.net/10725/5376 http://dx.doi.org/10.1007/978-3-319-19315-1_1 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. http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-319-19315-1_1 |
| dc.language.none.fl_str_mv | en |
| dc.publisher.none.fl_str_mv | Springer |
| dc.rights.*.fl_str_mv | info:eu-repo/semantics/openAccess |
| dc.title.none.fl_str_mv | On the complexity of various parameterizations of common induced subgraph isomorphism Combinatorial Algorithms |
| dc.type.none.fl_str_mv | Conference Paper / Proceeding info:eu-repo/semantics/publishedVersion info:eu-repo/semantics/conferenceObject |
| description | 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. |
| eu_rights_str_mv | openAccess |
| format | conferenceObject |
| id | LAURepo_cbb4f8b0ae59868990ae901b9542ee3a |
| identifier_str_mv | 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. |
| language_invalid_str_mv | en |
| network_acronym_str | LAURepo |
| network_name_str | Lebanese American University repository |
| oai_identifier_str | oai:laur.lau.edu.lb:10725/5376 |
| publishDate | 2017 |
| publisher.none.fl_str_mv | Springer |
| repository.mail.fl_str_mv | |
| repository.name.fl_str_mv | |
| repository_id_str | |
| spelling | On the complexity of various parameterizations of common induced subgraph isomorphismCombinatorial AlgorithmsAbu-Khzam, Faisal N.Bonnet, EdouardSikora, FlorianMaximum 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.N/ASpringer2017-03-16T11:01:33Z2017-03-16T11:01:33Z2017-03-16Conference Paper / Proceedinginfo:eu-repo/semantics/publishedVersioninfo:eu-repo/semantics/conferenceObjecthttp://hdl.handle.net/10725/5376http://dx.doi.org/10.1007/978-3-319-19315-1_1Abu-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.http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.phphttps://link.springer.com/chapter/10.1007/978-3-319-19315-1_1eninfo:eu-repo/semantics/openAccessoai:laur.lau.edu.lb:10725/53762021-03-19T10:03:24Z |
| spellingShingle | On the complexity of various parameterizations of common induced subgraph isomorphism Abu-Khzam, Faisal N. |
| status_str | publishedVersion |
| title | On the complexity of various parameterizations of common induced subgraph isomorphism |
| title_full | On the complexity of various parameterizations of common induced subgraph isomorphism |
| title_fullStr | On the complexity of various parameterizations of common induced subgraph isomorphism |
| title_full_unstemmed | On the complexity of various parameterizations of common induced subgraph isomorphism |
| title_short | On the complexity of various parameterizations of common induced subgraph isomorphism |
| title_sort | On the complexity of various parameterizations of common induced subgraph isomorphism |
| url | http://hdl.handle.net/10725/5376 http://dx.doi.org/10.1007/978-3-319-19315-1_1 http://libraries.lau.edu.lb/research/laur/terms-of-use/articles.php https://link.springer.com/chapter/10.1007/978-3-319-19315-1_1 |