zbMATH — the first resource for mathematics

Efficient algorithms for subgraph listing. (English) Zbl 07042205
Summary: Subgraph isomorphism is a fundamental problem in graph theory. In this paper we focus on listing subgraphs isomorphic to a given pattern graph. First, we look at the algorithm due to Chiba and Nishizeki for listing complete subgraphs of fixed size, and show that it cannot be extended to general subgraphs of fixed size. Then, we consider the algorithm due to L. Gąsieniec et al. [Inf. Process. Lett. 109, No. 4, 242–247 (2009; Zbl 1190.65073)] for finding multiple witnesses of a Boolean matrix product, and use it to design a new output-sensitive algorithm for listing all triangles in a graph. As a corollary, we obtain an output-sensitive algorithm for listing subgraphs and induced subgraphs isomorphic to an arbitrary fixed pattern graph.
05 Combinatorics
68 Computer science
Full Text: DOI
[1] Garey, M.R.; Johnson, D.S.; ; Computers and Intractability—A Guide to the Theory of NP-Completeness: Murray Hill, NJ, USA 1979; . · Zbl 0411.68039
[2] Chiba, N.; Nishizeki, T.; Arboricity and subgraph listing algorithms; SIAM J. Comput.: 1985; Volume 14 ,210-223. · Zbl 0572.68053
[3] Itai, A.; Rodeh, M.; Finding a minimum circuit in a graph; SIAM J. Comput.: 1978; Volume 7 ,413-423. · Zbl 0386.68064
[4] Gibbons, A.; ; Algorithmic Graph Theory: Cambridge, UK 1985; . · Zbl 0568.05001
[5] Gąsieniec, L.; Kowaluk, M.; Lingas, A.; Faster multi-witnesses for Boolean matrix multiplication; Inf. Process. Lett.: 2009; Volume 109 ,242-247. · Zbl 1190.65073
[6] Nes̆etr̆il, J.; Poljak, S.; On the complexity of the subgraph problem; Comment. Math. Univ. Carol.: 1985; Volume 26 ,415-419. · Zbl 0571.05050
[7] Schank, T.; Wagner, D.; Finding, counting and listing all triangles in large graphs, an experimental study; Proceedings of the 4th International Workshop, WEA 2005: ; ,606-609. · Zbl 1121.68360
[8] Vassilevska Williams, V.; Multiplying matrices faster than coppersmith-winograd; Proceedings of the 44th Symposium on Theory of Computing Conference (STOC 2012): ; ,887-898. · Zbl 1286.65056
[9] Coppersmith, D.; Winograd, S.; Matrix multiplication via arithmetic progressions; J. Symb. Comput.: 1990; Volume 9 ,251-280. · Zbl 0702.65046
[10] Cormen, T.; Leiserson, C.; Rivest, R.; ; Introduction to Algorithms: Cambridge, MA, USA 1990; . · Zbl 1158.68538
[11] Dvorak, Z.; Tuma, V.; A dynamic data structure for counting subgraphs in sparse graphs; Proceedings of the 13th International Symposium, WADS 2013: Berlin, Heidelberg, Germany 2013; ,304-315. · Zbl 1390.68208
[12] Kuramochi, M.; Karypis, G.; Finding frequent patterns in a large sparse graph; Data Min. Knowl. Discov.: 2005; Volume 11 ,243-271.
[13] Le Gall, F.; Faster algorithms for rectangular matrix multiplication; Proceedings of the 53rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2012): ; ,514-523.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.