Abstract
We study the complexity of frequent subtree mining in very simple graphs beyond forests. We show for d-tenuous outerplanar graphs that frequent subtrees can be listed with polynomial delay if the cycle degree, i.e., the maximum number of blocks that share a common vertex, is bounded by some constant. The crucial step in the proof of this positive result is a polynomial time algorithm deciding subgraph isomorphism from trees into d-tenuous outerplanar graphs of bounded cycle degree. We obtain this algorithm by generalizing the algorithm of Shamir and Tsur that decides subgraph isomorphism between trees. Our results may also be of some interest to algorithmic graph theory, as they indicate that even for very simple structures, the cycle degree is a crucial parameter for the tractability of subgraph isomorphism. We also discuss some interesting problems towards generalizing the positive result of this work.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Similar content being viewed by others
Notes
- 1.
http://cactus.nci.nih.gov/download/nci, Release 4 File Series.
- 2.
We recall that by condition, G contains at least one edge.
- 3.
References
Agrawal, R., Mannila, H., Srikant, R., Toivonen, H., Verkamo, A.I.: Fast discovery of association rules. In: Advances in Knowledge Discovery and Data Mining, pp. 307–328. AAAI/MIT Press (1996)
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)
Chi, Y., Yang, Y., Muntz, R.R.: Indexing and mining free trees. In: ICDM, pp. 509–512. IEEE Computer Society (2003)
De Raedt, L.: Logical and Relational Learning. Cognitive Technologies. Springer, Heidelberg (2008)
Diestel, R.: Graph Theory, vol. 173. Springer, Heidelberg (2012)
Garriga, G.C., Khardon, R., De Raedt, L.: Mining closed patterns in relational, graph and network data. Ann. Math. Artif. Intell. 69(4), 315–342 (2013)
Gottlob, G.: Subsumption and implication. Inf. Process. Lett. 24(2), 109–111 (1987)
Hajiaghayi, M., Nishimura, N.: Subgraph isomorphism, log-bounded fragmentation, and graphs of (locally) bounded treewidth. J. Comput. Syst. Sci. 73(5), 755–768 (2007)
Han, J., Pei, J., Yin, Y., Mao, R.: Mining frequent patterns without candidate generation: a frequent-pattern tree approach. Data Min. Knowl. Discov. 8(1), 53–87 (2004)
Harary, F.: Graph Theory. Addison-Wesley Series in Mathematics. Perseus Books, Boulder (1994)
Hopcroft, J.E., Karp, R.M.: An \({\rm n}^{\wedge }5/2\) algorithm for maximum matchings in bipartite graphs. SIAM J. Comput. 2(4), 225–231 (1973)
Horváth, T., Ramon, J.: Efficient frequent connected subgraph mining in graphs of bounded tree-width. Theor. Comput. Sci. 411(31–33), 2784–2797 (2010)
Horváth, T., Ramon, J., Wrobel, S.: Frequent subgraph mining in outerplanar graphs. Data Min. Knowl. Discov. 21(3), 472–508 (2010)
Horváth, T., Turán, G.: Learning logic programs with structured background knowledge. Artif. Intell. 128(1–2), 31–97 (2001)
Johnson, D.S., Yannakakis, M., Papadimitriou, C.H.: On generating all maximal independent sets. Inf. Process. Lett. 27(3), 119–123 (1988)
Matoušek, J., Thomas, R.: On the complexity of finding iso-and other morphisms for partial \(k\)-trees. Discrete Math. 108(1), 343–364 (1992)
Read, R.C., Tarjan, R.: Bound on backtrack algorithms for listing cycles, paths, and spanning trees. Networks 5, 237–252 (1975)
Shamir, R., Tsur, D.: Faster subtree isomorphism. In: Proceedings of the Fifth Israeli Symposium on the Theory of Computing and Systems, pp. 126–131. IEEE (1997)
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
Welke, P., Horváth, T., Wrobel, S. (2015). On the Complexity of Frequent Subtree Mining in Very Simple Structures. In: Davis, J., Ramon, J. (eds) Inductive Logic Programming. Lecture Notes in Computer Science(), vol 9046. Springer, Cham. https://doi.org/10.1007/978-3-319-23708-4_14
Download citation
DOI: https://doi.org/10.1007/978-3-319-23708-4_14
Published:
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-23707-7
Online ISBN: 978-3-319-23708-4
eBook Packages: Computer ScienceComputer Science (R0)