Article in press
Authors:
Title:
Maximum common induced subforests and minimum common induced superforests of a set of forests
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-08-12 , Revised: 2025-09-01 , Accepted: 2025-09-01 , Available online: 2025-10-27 , https://doi.org/10.7151/dmgt.2606
Abstract:
Graph isomorphism, subgraph isomorphism, and maximum common subgraphs are
classical well-investigated objects. In the present paper, for a given set of
forests, we study maximum common induced subforests and minimum common induced
superforests. We show that finding a maximum subforest is NP-hard for two given
subdivided stars while finding a minimum superforest is tractable for two trees
but NP-hard for three trees. For a given set of $k$ trees, we present an
efficient greedy $\left(\frac{k}{2}-\frac{1}{2}+\frac{1}{k}\right)$-approximation
algorithm for the minimum superforest problem. Finally, we present a polynomial
time approximation scheme for the maximum subforest problem for any given set
of forests.
Keywords:
subgraph isomorphism, common subgraph
References:
- A. Abboud, A. Backurs, T.D. Hansen, V.V. Williams and O. Zamir, Subtree isomorphism revisited, ACM Trans. Algorithms 14 (2018) 27.
https://doi.org/10.1145/3093239 - F.N. Abu-Khzam, Maximum common induced subgraph parameterized by vertex cover, Inform. Process. Lett. 114 (2014) 99–103.
https://doi.org/10.1016/j.ipl.2013.11.007 - F.N. Abu-Khzam, É. Bonnet and F. Sikora, On the complexity of various parameterizations of common induced subgraph isomorphism, Theoret. Comput. Sci. 697 (2017) 69–78.
https://doi.org/10.1016/j.tcs.2017.07.010 - T. Akutsu, An RNC algorithm for finding a largest common subtree of two trees, IEICE Trans. Inf. Syst. E75-D (1992) 95–101.
- T. Akutsu, A.A. Melkman and T. Tamura, Improved hardness of maximum common subgraph problems on labeled graphs of bounded treewidth and bounded degree, Internat. J. Found. Comput. Sci. 31 (2020) 253–273.
https://doi.org/10.1142/S0129054120500069 - T. Akutsu and T. Tamura, On the complexity of the maximum common subgraph problem for partial $k$-trees of bounded degree, in: Algorithms and Computation ISAAC 2012, K.M. Chao, Ts.Hsu and D.T.Lee (Ed(s)), Lect. Notes in Comput. Sci. 7676, (Springer, Berlin, Heidelberg, 2012) 146–155.
https://doi.org/10.1007/978-3-642-35261-4\_18 - H.L. Bodlaender, T. Hanaka, Y. Kobayashi, Y. Kobayashi, Y. Okamoto, Y. Otachi and T.C. van der Zanden, Subgraph isomorphism on graph classes that exclude a substructure, Algorithmica 82 (2020) 3566–3587.
https://doi.org/10.1007/s00453-020-00737-z - S.H. Bokhari, On the mapping problem, IEEE Trans. Comput. 30 (1981) 207–214.
https://doi.org/10.1109/TC.1981.1675756 - M. Cygan, Improved approximation for $3$-dimensional matching via bounded pathwidth local search, in: 2013 IEEE 54th Annual Symposium on Foundations of Computer Science (2013) 509–518.
https://doi.org/10.1109/FOCS.2013.61 - M.R. Garey and D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (Freeman, San Francisco, 1979).
https://doi.org/10.1137/1024022 - M. Grohe, G. Rattan and G.J. Woeginger, Graph similarity and approximate isomorphism, in: 43rd International Symposium on Mathematical Foundations of Computer Science (MFCS 2018), Leibniz International Proceedings in Informatics (LIPIcs) 117, (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2018) 20.
https://doi.org/10.4230/LIPIcs.MFCS.2018.20 - P. Heggernes, P. van 't Hof, D. Meister and Y. Villanger, Induced subgraph isomorphism on proper interval and bipartite permutation graphs, Theoret. Comput. Sci. 562 (2015) 252–269.
https://doi.org/10.1016/j.tcs.2014.10.002 - C.A.J. Hurkens and A. Schrijver, On the size of systems of sets every t of which have an SDR, with an application to the worst-case ratio of heuristics for packing problems, SIAM J. Discrete Math. 2 (1989) 68–72.
https://doi.org/10.1137/0402008 - N. Kriege, F. Kurpicz and P. Mutzel, On maximum common subgraph problems in series-parallel graphs, European J. Combin. 68 (2018) 79–95.
https://doi.org/10.1016/j.ejc.2017.07.012 - D.W. Matula, Subtree isomorphism in $O(n^{5/2})$, Ann. Discrete Math. 2 (1978) 91–106.
https://doi.org/10.1016/S0167-5060(08)70324-8 - D. Marx and M. Pilipczuk, Everything you always wanted to know about the parameterized complexity of subgraph isomorphism $($but were afraid to ask$)$, in: 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014), LIPIcs. Leibniz Int. Proc. Inform. 25, (Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2014) 542–553.
https://doi.org/10.4230/LIPIcs.STACS.2014.542 - J.W. Raymond and P. Willett, Maximum common subgraph isomorphism algorithms for the matching of chemical structures, J. Comput. Aided Mol. Des. 16 (2002) 521–533.
https://doi.org/10.1023/A:1021271615909 - K. Shearer, H. Bunke and S. Venkatesh, Video indexing and similarity retrieval by largest common subgraph detection using decision trees, Pattern Recognition 34 (2001) 1075–1091.
https://doi.org/10.1016/S0031-3203(00)00048-0 - A. Yamaguchi, K.F Aoki and H. Mamitsuka, Finding the maximum common subgraph of a partial $k$-tree and a graph with a polynomially bounded number of spanning trees, Inform. Process. Lett. 92 (2004) 57–63.
https://doi.org/10.1016/j.ipl.2004.06.019
Close