Efficient algorithms for subgraph listing (Q1736617)

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 \textit{N. Chiba} and \textit{T. Nishizeki} [SIAM J. Comput. 14, 210--223 (1985; Zbl 0572.68053)] 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 \textit{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.