## 1 Introduction  
We shall consider undirected graphs. The decision version of the subgraph isomorphism problem is to decide if a host graph has a subgraph isomorphic to a pattern graph. The search version asks for finding a subgraph of the host graph isomorphic to the pattern graph. In the counting version, the number of subgraphs of the host graph isomorphic to the pattern graph should be reported. Finally, the listing version asks for a list of all subgraphs of the host graph isomorphic to the pattern graph. A subgraph of the host graph is induced if it retains all edges of the host graph between its nodes. By replacing \"subgraph\" with \"induced subgraph\", we obtain the corresponding versions of induced subgraph isomorphism. The decision versions of subgraph isomorphism and induced subgraph isomorphism are NP-complete in general. Special cases of these problems include the independent set, clique, Hamiltonian cycle, and Hamiltonian path, all of which are known to be NP-complete [1]. However, for pattern graphs of fixed size, all these problems admit polynomial-time solutions. Namely, for a pattern graph with \(p=\text{O}(1)\) nodes and a host graph with \(n\) nodes, the brute force method yields a solution in \(\text{O}(n^{p})\) time. Since there might be up to \(\Omega(n^{p})\) subgraphs or induced subgraphs isomorphic to the pattern graph, the brute force method cannot be substantially asymptotically improved in case of the listing versions in general. This however does not exclude the possibility of faster listing algorithms for restricted graph classes and output-sensitive algorithms whose complexity depends on the size of the output list of isomorphic subgraphs. In the first part of this paper, we look at an algorithm by [PERSON] and [PERSON] [2], which lists all occurrences of complete subgraphs of size \(s\). It assumes that the host graph has bounded arboricity. The arboricity of a graph is the minimum number of forests (_i.e._, sets of edge-disjoint trees) that are needed to cover the graph. The algorithm runs in \(\text{O}(sma^{s-2})\) time, where \(a\) is the arboricity of the host graph and \(m\) is its number of edges. We show that this upper bound on the running time cannot be extended to general pattern graphs--for any pattern graph that is connected but not complete, the time has to be at least quadratic in the number of nodes of the host graph. In the second part, we consider the problem of listing all triangles, that is, complete subgraphs of size three (_cf._[3]). Using the matrix product, we can find out which of the edges participate in any triangle, and how many triangles each of them belongs to [4]. Then, in order to list the triangles, we use the \(k\)-witness algorithm developed by [PERSON] _et al._[5]. It finds multiple witnesses of a Boolean matrix product (see Preliminaries), which can be used to list for each edge the triangles it participates in. The \(k\)-witness algorithm takes a parameter \(k\) and finds for each entry all the witnesses up to a maximum of \(k\) witnesses, so it is useful when no edge is in more than a small number of triangles. We devise a new algorithm, which uses the \(k\)-witness algorithm for those edges that are in few triangles, and otherwise a straightforward method checking all nodes incident to an endpoint of an examined edge. We show that the asymptotic time of this combined algorithm is less than that of the brute force algorithm in all cases except when the number of triangles is nearly cubic. For a graph with \(n\) nodes and \(l\) triangles, our combined algorithm lists all triangles in time \(\widetilde{\text{O}}(n^{2.3727})\) for \(l<n^{1.3727}\), \(\widetilde{\text{O}}(n^{1.9368}l^{0.31754})\) for \(n^{1.3727}\leqslant l<n^{2.3940},\) and \(\widetilde{\text{O}}(n^{1.5}l^{0.5})\) for \(n^{2.3940}\leqslant l<n^{3}\), where \(\widetilde{\text{O}}(f)\) stands for \(\text{O}(f^{1+\text{o}(1)})\). [PERSON] and [PERSON] present a straightforward reduction of subgraph isomorphism or induced subgraph isomorphism to triangle detection [6].