Abstract
Maximum Common Induced Subgraph (henceforth MCIS) is among the most studied classical \({\mathsf {NP}}\)-hard problems. MCIS remains \({\mathsf {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 \({\mathsf {NP}}\subseteq \mathsf {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 \({\mathsf {W[1]}}\)-complete on bipartite graphs and graphs of girth five and, unless \({\mathsf {P}}= {\mathsf {NP}}\), they do not belong to the class \({\mathsf {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.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
References
Abu-Khzam, F.N.: Maximum common induced subgraph parameterized by vertex cover. Inf. Process. Lett. 114(3), 99–103 (2014)
Akutsu, T.: An RNC algorithm for finding a largest common subtree of two trees. IEICE Trans. Inf. Syst. 75(1), 95–101 (1992)
Akutsu, T.: A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 76(9), 1488–1493 (1993)
Bodlaender, H.L., Jansen, B.M.P., Kratsch, S.: Kernelization lower bounds by cross-composition. SIAM J. Discrete Math. 28(1), 277–305 (2014)
Cesati, M.: The turing way to parameterized complexity. J. Comput. Syst. Sci. 67(4), 654–685 (2003)
Chen, J., Kanj, I.A., Xia, G.: Improved upper bounds for vertex cover. Theor. Comput. Sci. 411(40–42), 3736–3756 (2010)
Downey, R.G., Fellows, M.R.: Fundamentals of Parameterized Complexity. Texts in Computer Science. Springer, London (2013)
Fellows, M.R., Jansen, B.M.P., Rosamond, F.A.: Towards fully multivariate algorithmics: parameter ecology and the deconstruction of computational complexity. Eur. J. Comb. 34(3), 541–566 (2013)
Flum, J., Grohe, M.: Fixed-parameter tractability, definability, and model-checking. SIAM J. Comput. 31(1), 113–145 (2001)
Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP-Completeness. W.H. Freeman, San Francisco (1979)
Grindley, H.M., Artymiuk, P.J., Rice, D.W., Willett, P.: Identification of tertiary structure resemblance in proteins using a maximal common subgraph isomorphism algorithm. J. Mol. Biol. 229(3), 707–721 (1993)
Koch, I., Lengauer, T., Wanke, E.: An algorithm for finding maximal common subtopologies in a set of protein structures. J. Comput. Biol. 3(2), 289–306 (1996)
McGregor, J., Willett, P.: Use of a maximal common subgraph algorithm in the automatic identification of the ostensible bond changes occurring in chemical reactions. J. Chem. Inf. Comput. Sci 21, 137–140 (1981)
Moser, H., Sikdar, S.: The parameterized complexity of the induced matching problem. Discrete Appl. Math. 157(4), 715–727 (2009)
Niedermeier, R.: Invitation to Fixed Parameter Algorithms. Lecture Series in Mathematics and Its Applications. Oxford University Press, Oxford (2006)
Raymond, J.W., Willett, P.: Maximum common subgraph isomorphism algorithms for the matching of chemical structures. J. Comput. Aided Mol. Des. 16, 521–533 (2002)
Yamaguchi, A., Aoki, K.F., Mamitsuka, H.: Finding the maximum common subgraph of a partial k-tree and a graph with a polynomially bounded number of spanning trees. Inf. Process. Lett. 92(2), 57–63 (2004)
Acknowledgements
Work partially supported by the bilateral research cooperation CEDRE between France and Lebanon (grant number 30885TM).
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2015 Springer International Publishing Switzerland
About this paper
Cite this paper
Abu-Khzam, F.N., Bonnet, É., Sikora, F. (2015). On the Complexity of Various Parameterizations of Common Induced Subgraph Isomorphism. In: Jan, K., Miller, M., Froncek, D. (eds) Combinatorial Algorithms. IWOCA 2014. Lecture Notes in Computer Science(), vol 8986. Springer, Cham. https://doi.org/10.1007/978-3-319-19315-1_1
Download citation
DOI: https://doi.org/10.1007/978-3-319-19315-1_1
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-19314-4
Online ISBN: 978-3-319-19315-1
eBook Packages: Computer ScienceComputer Science (R0)