## 4 A Combined Algorithm for Listing of Triangles
### Listing Subgraphs Isomorphic to an Arbitrary Pattern Graph  
The reduction of subgraph isomorphism or induced subgraph isomorphism to triangle detection from [6] also works for the counting and listing versions. By using the aforementioned reduction, we can also generalize our combined algorithm to include listing of subgraphs or induced subgraphs isomorphic to an arbitrary fixed pattern graph. For the sake of completeness, we shall outline the reduction for listing the subgraphs isomorphic to the pattern graph.  
Let \(h\) be the number of nodes in the fixed pattern graph \(H,\) and let \(f=\lceil h/3\rceil\). Since \(F\) is fixed, we have \(h=\mathsf{O}(1)\) and \(f=\mathsf{O}(1)\). Divide the pattern graph into three subgraphs \(H_{i},\)\(i=1,2,3,\) each having \(f\) or \(\lfloor h/3\rfloor\) nodes. Form a new graph \(G^{\prime}\) in which each node \(v\) corresponds one to one to a pair \((G_{v},\phi_{v}),\) where \(G_{v}\) is a subgraph of the original graph \(G\) and \(\phi_{v}\) is an isomorphism between \(H_{i}\) for some \(i\in\{1,2,3\}\) and \(G_{v}.\) Two nodes \(v\) and \(u\) in \(G^{\prime}\) are connected by an edge if and only if  
1. \(G_{v}\) and \(G_{u}\) are node-disjoint and the isomorphisms \(\phi_{v},\ \phi_{u}\) are defined on two distinct parts of \(H\), \(H_{i_{v}}\) and \(H_{i_{u}}\), and
2. the union of the isomorphisms \(\phi_{v},\ \phi_{u}\) yields an isomorphism between the subgraph of \(H\) induced by the nodes of \(H_{i_{v}}\) and \(H_{i_{u}}\), and the subgraph of \(G\) consisting of \(G_{v}\) and \(G_{u}\), and some edges of \(G\) between \(G_{v}\) and \(G_{u}\).  
Observe that \(G^{\prime}\) has \(\mathsf{O}(n^{f}f!)=\mathsf{O}(n^{f})\) nodes. By \(f=\mathsf{O}(1),\) they can be be listed in \(\mathsf{O}(n^{f})\) time. For a given pair of nodes \(v,\ u\) of \(G^{\prime}\), the necessary and sufficient conditions for making them adjacent can also be verified in \(\mathsf{O}(1)\) time. It follows that \(G^{\prime}\) can be constructed in \(\mathsf{O}(n^{2f})\) time. Furthermore, triangles in \(G^{\prime}\) are in one-to-one correspondence with isomorphisms between \(H\) and a subgraph of \(G\) isomorphic to \(H.\) Therefore, by using Theorem 4 to list all triangles in \(G^{\prime}\), we can determine and list all subgraphs of \(G\) isomorphic to \(H\) in time resulting from the substitution of \(\mathsf{O}(n^{f})\) for \(n\) in the upper bounds of Theorem 4. By replacing \"subgraph\" with \"induced subgraph\", we obtain the analogous reduction for listing induced subgraphs isomorphic to \(H\).  
**Theorem 7**.: _Let \(H\) be an arbitrary fixed pattern graph with \(h\) nodes. For a graph with \(n\) nodes and \(l\) subgraphs (induced subgraphs, respectively) isomorphic to \(H\), all the subgraphs can be listed in time \(\widetilde{\mathsf{O}}(n^{2.3727\lceil h/3\rceil})\), if \(l<n^{1.3727\lceil h/3\rceil}\)_  
\(\widetilde{\mathsf{O}}(n^{1.9368\lceil h/3\rceil}0^{.31754})\)_, if \(n^{1.3727\lceil h/3\rceil}\leqslant l<n^{2.3940\lceil h/3\rceil}\)_  
\(\widetilde{\mathsf{O}}(n^{1.5\lceil h/3\rceil}l^{0.5})\)_, if \(n^{2.3940\lceil h/3\rceil}\leqslant l<n^{3\lceil h/3\rceil}.\)_