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...
Saved in:
| Main Author: | |
|---|---|
| Other Authors: | , |
| Format: | conferenceObject |
| Published: |
2017
|
| Online Access: | 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 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Summary: | 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. |
|---|