{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,30]],"date-time":"2026-04-30T11:30:21Z","timestamp":1777548621310,"version":"3.51.4"},"reference-count":37,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,12,30]],"date-time":"2014-12-30T00:00:00Z","timestamp":1419897600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["IIS-1217869"],"award-info":[{"award-number":["IIS-1217869"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2014,12,30]]},"abstract":"<jats:p>\n            A\n            <jats:italic>frequent subgraph<\/jats:italic>\n            of a given collection of graphs is a graph that is isomorphic to a subgraph of at least as many graphs in the collection as a given threshold. Frequent subgraphs generalize frequent itemsets and arise in various contexts, from bioinformatics to the Web. Since the space of frequent subgraphs is typically extremely large, research in graph mining has focused on special types of frequent subgraphs that can be orders of magnitude smaller in number, yet encapsulate the space of all frequent subgraphs.\n            <jats:italic>Maximal<\/jats:italic>\n            frequent subgraphs (i.e., the ones not properly contained in any frequent subgraph) constitute the most useful such type.\n          <\/jats:p>\n          <jats:p>In this article, we embark on a comprehensive investigation of the computational complexity of mining maximal frequent subgraphs. Our study is carried out by considering the effect of three different parameters: possible restrictions on the class of graphs; a fixed bound on the threshold; and a fixed bound on the number of desired answers. We focus on specific classes of connected graphs: general graphs, planar graphs, graphs of bounded degree, and graphs of bounded treewidth (trees being a special case). Moreover, each class has two variants: that in which the nodes are unlabeled, and that in which they are uniquely labeled. We delineate the complexity of the enumeration problem for each of these variants by determining when it is solvable in (total or incremental) polynomial time and when it is NP-hard. Specifically, for the labeled classes, we show that bounding the threshold yields tractability but, in most cases, bounding the number of answers does not, unless P=NP; an exception is the case of labeled trees, where bounding either of these two parameters yields tractability. The state of affairs turns out to be quite different for the unlabeled classes. The main (and most challenging to prove) result concerns unlabeled trees: we show NP-hardness, even if the input consists of two trees and both the threshold and the number of desired answers are equal to just two. In other words, we establish that the following problem is NP-complete: given two unlabeled trees, do they have more than one maximal subtree in common?<\/jats:p>","DOI":"10.1145\/2629550","type":"journal-article","created":{"date-parts":[[2015,1,5]],"date-time":"2015-01-05T13:27:09Z","timestamp":1420464429000},"page":"1-33","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":18,"title":["The Complexity of Mining Maximal Frequent Subgraphs"],"prefix":"10.1145","volume":"39","author":[{"given":"Benny","family":"Kimelfeld","sequence":"first","affiliation":[{"name":"LogicBlox, Inc., Atlanta, GA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Phokion G.","family":"Kolaitis","sequence":"additional","affiliation":[{"name":"University of California, Santa Cruz and IBM Research -- Almaden, San Jose, CA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,12,30]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808746"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1024605820527"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB'06)","author":"Cohen Sara","year":"2006","unstructured":"Sara Cohen , Itzhak Fadida , Yaron Kanza , Benny Kimelfeld , and Yehoshua Sagiv . 2006 . Full disjunctions: Polynomial-delay iterators in action . In Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB'06) . ACM Press, New York, 739--750. Sara Cohen, Itzhak Fadida, Yaron Kanza, Benny Kimelfeld, and Yehoshua Sagiv. 2006. Full disjunctions: Polynomial-delay iterators in action. In Proceedings of the 32nd International Conference on Very Large Data Bases (VLDB'06). ACM Press, New York, 739--750."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.127"},{"key":"e_1_2_1_5_1","volume-title":"Fellows","author":"Downey Rodney G.","year":"1999","unstructured":"Rodney G. Downey and Michael R . Fellows . 1999 . Parameterized Complexity. Springer . Rodney G. Downey and Michael R. Fellows. 1999. Parameterized Complexity. Springer."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205049"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2005.63"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2006.05.001"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2006.173"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/777943.777945"},{"key":"e_1_2_1_11_1","volume-title":"Hopcroft and Robert Endre Tarjan","author":"John","year":"1972","unstructured":"John E. Hopcroft and Robert Endre Tarjan . 1972 . Isomorphism of planar graphs. In Complexity of Computer Computations. The IBM Research Symposia Series. Plenum Press , New York, 131--152. John E. Hopcroft and Robert Endre Tarjan. 1972. Isomorphism of planar graphs. In Complexity of Computer Computations. The IBM Research Symposia Series. Plenum Press, New York, 131--152."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014123"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.5555\/645804.669817"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1021726221443"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(88)90065-8"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00454-008-9050-5"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2463664.2465222"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265572"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/645496.658027"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.33"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0166-218X(95)00092-6"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/0012-365X(92)90687-B"},{"key":"e_1_2_1_23_1","volume-title":"Jude Shavlik, In\u0142s Dutra, David Page, and Vitor Santos Costa.","author":"Mooney Raymond J.","year":"2004","unstructured":"Raymond J. Mooney , Prem Melville , Rupert Lapoon Tang , Jude Shavlik, In\u0142s Dutra, David Page, and Vitor Santos Costa. 2004 . Relational data mining with inductive logic programming for link discovery. In Data Mining: Next Generation Challenges and Future Directions, AAAI Press , 239--254. Raymond J. Mooney, Prem Melville, Rupert Lapoon Tang, Jude Shavlik, In\u0142s Dutra, David Page, and Vitor Santos Costa. 2004. Relational data mining with inductive logic programming for link discovery. In Data Mining: Next Generation Challenges and Future Directions, AAAI Press, 239--254."},{"key":"e_1_2_1_24_1","volume-title":"Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics (SMC'04)","volume":"5","author":"Nijssen Siegfried","unstructured":"Siegfried Nijssen and Joost N. Kok . 2004. Frequent graph mining and its application to molecular databases . In Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics (SMC'04) . Vol. 5 , 4571--4577. Siegfried Nijssen and Joost N. Kok. 2004. Frequent graph mining and its application to molecular databases. In Proceedings of the IEEE International Conference on Systems, Man, and Cybernetics (SMC'04). Vol. 5, 4571--4577."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2006.07.006"},{"key":"e_1_2_1_26_1","volume-title":"Proceedings of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. 21--30","author":"Pei Jian","year":"2000","unstructured":"Jian Pei , Jiawei Han , and Runying Mao . 2000 . CLOSET: An efficient algorithm for mining frequent closed itemsets . In Proceedings of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. 21--30 . Jian Pei, Jiawei Han, and Runying Mao. 2000. CLOSET: An efficient algorithm for mining frequent closed itemsets. In Proceedings of the ACM SIGMOD Workshop on Research Issues in Data Mining and Knowledge Discovery. 21--30."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CSE.2009.225"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1839490.1839491"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221023"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(79)90044-6"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5555\/2017990.2018006"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956779"},{"key":"e_1_2_1_34_1","volume-title":"Proceedings of the IEEE International Conference on Data Mining (ICDM'02)","author":"Yan Xifeng","year":"2002","unstructured":"Xifeng Yan and Jiawei Han . 2002 . gSpan: Graph-based substructure pattern mining . In Proceedings of the IEEE International Conference on Data Mining (ICDM'02) . IEEE Computer Society, 721--724. Xifeng Yan and Jiawei Han. 2002. gSpan: Graph-based substructure pattern mining. In Proceedings of the IEEE International Conference on Data Mining (ICDM'02). IEEE Computer Society, 721--724."},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/956750.956784"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/1014052.1014091"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611972726.27"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629550","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2629550","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:01:18Z","timestamp":1750230078000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2629550"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,30]]},"references-count":37,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,12,30]]}},"alternative-id":["10.1145\/2629550"],"URL":"https:\/\/doi.org\/10.1145\/2629550","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,12,30]]},"assertion":[{"value":"2013-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-02-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2014-12-30","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}