We consider the maximum common connected edge subgraph problem and the maximum common connected induced subgraph problem for simple graphs with labeled vertices (or labeled edges). The former is to find a connected graph with the maximum number of edges that is isomorphic to a subgraph of each of the two input graphs. The latter is to find a common connected induced subgraph with the maximum number of vertices. We prove that both problems are NP-hard for 3-outerplanar labeled graphs even if the maximum vertex degree is bounded by 4. Since the reductions used in the proofs construct graphs with treewidth at most 4, both problems are NP-hard also for such graphs, which significantly improves the previous hardness results for graphs with treewidth 11. We also present improved exponential-time algorithms for both problems on labeled graphs of bounded treewidth and bounded vertex degree.

A preliminary version of this paper appeared as a conference paper [3].

Communicated by Marek Chrobak

Keywords:

References

1. F. N. Abu-Khzam, Maximum common induced subgraph parameterized by vertex cover, Inform. Process. Lett. 114 (2014) 99–103. Crossref, Web of Science, Google Scholar
2. F. N. Abu-Khzam, E. Bonnet and F. Sikora, On the complexity of various parameterizations of common induced subgraph isomorphism. Theoret. Comput. Sci. 697 (2017) 69–78. Crossref, Web of Science, Google Scholar
3. F. N. Abu-Khzam et al., The maximum common subgraph problem: Faster solutions via vertex cover, Proc. 2007 IEEE/ACS Int. Conf. Computer Systems and Applications (IEEE, New Jersey, 2007), pp. 367–373. Crossref, Google Scholar
4. T. Akutsu, A polynomial time algorithm for finding a largest common subgraph of almost trees of bounded degree, IEICE Trans. Fundamentals E76-A (1993) 1488–1493. Google Scholar
5. T. Akutsu and T. Tamura, On the complexity of the maximum common subgraph problem for partial $k$ -trees of bounded degree, Proc. 23rd International Symposium on Algorithms and Computation, Lecture Notes in Computer Science, Vol. 7676 (Springer, Berlin, 2012), pp. 146–155. Crossref, Google Scholar
6. T. Akutsu and T. Tamura, A polynomial-time algorithm for computing the maximum common connected edge subgraph of outerplanar graphs of bounded degree, Algorithms 6 (2013) 119–136. Crossref, Google Scholar
7. D. Avis and K. Fukuda, Reverse search for enumeration, Disc. Appl. Math. 65 (1996) 21–46. Crossref, Web of Science, Google Scholar
8. L. Cai, S. M. Chan and S. O. Chan, Random separation: a new method for solving fixed-cardinality optimization problems, Proc. 2nd Int. Workshop on Parameterized and Exact Computation, Lecture Notes in Computer Science, Vol. 4169 (Springer, Berlin, 2006), pp. 239–250. Crossref, Google Scholar
9. L. Babai, Graph isomorphism in quasipolynomial time, Proc. 47th ACM Symp. Theory of Computing (ACM Press, New York, 2016), pp. 684–697. Google Scholar
10. L. Babai and E. M. Luks, Canonical labeling of graphs, Proc. 15th ACM Symp. Theory of Computing (ACM Press, New York, 1983), pp. 171–183. Crossref, Google Scholar
11. S. Bachl, F.-J. Brandenburg and D. Gmach, Computing and drawing isomorphic subgraphs, J. Graph Algo. Appl. 8 (2004) 215–238. Crossref, Google Scholar
12. A. Björklund et al., The traveling salesman problem in bounded degree graphs, ACM Trans. Algorithms 8 (2012) 18:1–18:13. Crossref, Web of Science, Google Scholar
13. H. L. Bodlaender, A partial k-arboretum of graphs with bounded treewidth, Theoret. Comput. Sci. 209 (1989) 1–45. Crossref, Web of Science, Google Scholar
14. D. Conte et al., Thirty years of graph matching in pattern recognition, Int. J. Pattern Recognition and Artificial Intelligence 18 (2004) 265–298. Link, Web of Science, Google Scholar
15. E. Duesbury, J. D. Holliday and P. Willett, Maximum Common Subgraph Isomorphism Algorithms, MATCH Commun. Math. Comput. Chem. 77 (2017) 213–232. Web of Science, Google Scholar
16. J. Flum and M. Grohe, Fixed-parameter tractability, definability, and model checking, SIAM J. Computing 31 (2001) 113–145. Crossref, Web of Science, Google Scholar
17. M. Grohe, S. Kreutzer and S. Siebertz, Deciding first-order properties of nowhere dense graphs, J. ACM 64 (2017) 17. Crossref, Web of Science, Google Scholar
18. M. R. Garey and D. S. Johnson, Computers and Intractability (Freeman, New York, 1979). Google Scholar
19. M. Hajiaghayi and N. Nishimura, Subgraph isomorphism, log-bounded fragmentation and graphs of (locally) bounded treewidth, J. Comput. Syst. Sci. 73 (2007) 755–768. Crossref, Web of Science, Google Scholar
20. D. J. Harvey and D. R. Wood, The treewidth of line graphs, J. Combinatorial Theory Series B 132 (2018) 157–179. Crossref, Web of Science, Google Scholar
21. P. Heggernes et al., Induced Subgraph Isomorphism on proper interval and bipartite permutation graphs, Theoret. Comput. Sci. 562 (2015) 252–268. Crossref, Web of Science, Google Scholar
22. X. Huang, J. Lai and S. F. Jennings, Maximum common subgraph: some upper bound and lower bound results, BMC Bioinformatics 7 (Suppl. 4) (2006) S-4. Google Scholar
23. K. Kangas et al., On the number of connected sets in bounded degree graphs, Proc. 40th International Workshop on Graph-Theoretic Concepts in Computer Science (WG 2014), Lecture Notes in Computer Science, Vol. 8747 (Springer, 2014), pp. 336–347. Crossref, Google Scholar
24. I. Koch, Enumerating all connected maximal common subgraphs in two graphs, Theoret. Comput. Sci. 250 (2001) 1–30. Crossref, Web of Science, Google Scholar
25. N. Kriege, F. Kurpicz and P. Mutzel, On maximum common subgraph problems in series-parallel graphs, European Journal of Combinatorics 68 (2018) 79–95. Crossref, Web of Science, Google Scholar
26. E. M. Luks, Isomorphism of graphs of bounded valence can be tested in polynomial time, J. Comput. Syst. Sci. 25 (1982) 42–65. Crossref, Web of Science, Google Scholar
27. D. Marx and M. Pilipczuk, Everything you always wanted to know about the parameterized complexity of subgraph isomorphism (but were afraid to ask), Proc. 31st Symposium on Theoretical Aspects of Computer Science (online proceedings: http://www.dagstuhl.de/dagpub/978-3-939897-65-1), 2014, pp. 542–553. Google Scholar
28. J. Matoušek and R. Thomas, On the complexity of finding iso- and other morphisms for partial $k$ -trees, Discrete Math. 108 (1992) 343–364. Crossref, Web of Science, Google Scholar
29. V. Nicholson et al., A subgraph isomorphism theorem for molecular graphs, Stud. Phys. Theoret. Chem. 51 (1987) 226–230. Google Scholar
30. J. W. Raymond and P. Willett, Maximum common subgraph isomorphism algorithms for the matching of chemical structures, J. Computer-Aided Molecular Design 16 (2002) 521–533. Crossref, Web of Science, Google Scholar
31. L. Schietgat, J. Ramon and M. Bruynooghe, A polynomial-time maximum common subgraph algorithm for outerplanar graphs and its application to chemoinformatics, Ann. Math, Artif. Intell. 69 (2013) 343–376. Crossref, Web of Science, Google Scholar
32. P. D. Seymour and R. Thomas, Graph searching and a min-max theorem for tree-width, J. Comb. Theory, Ser. B 58 (1993) 22–33. Crossref, Web of Science, Google Scholar
33. 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. Crossref, Web of Science, Google Scholar
34. M. M. Syslo, The subgraph isomorphism problem for outerplanar graphs, Theoret. Comput. Sci. 17 (1982) 91–97. Crossref, Web of Science, Google Scholar
35. P. Vismara and B. Valery, Finding Maximum Common Connected Subgraphs Using Clique Detection or Constraint Satisfaction Algorithms, Proc. MCO2008, Communications in Computer and Information Science, Vol. 14 (Springer, 2008), pp. 358–368. Crossref, Google Scholar
36. H. Whitney, Congruent graphs and the connectivity of graphs, Am. J. Math. 54 (1932) 150–168. Crossref, Google Scholar
37. 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. Crossref, Web of Science, Google Scholar