text: Listing all triangles is a fundamental graph operation. Triangles can have important interpretations in real-world graphs, especially social and other interaction networks. Despite the lack of provably efficient (linear, or slightly super-linear) worst-case algorithms for this problem, practitioners run simple, efficient heuristics to find all triangles in graphs with millions of vertices. How are these heuristics exploiting the structure of these special graphs to provide major speedups in running time? We study one of the most prevalent algorithms used by practitioners. A trivial algorithm enumerates all paths of length @math , and checks if each such path is incident to a triangle. A good heuristic is to enumerate only those paths of length @math where the middle vertex has the lowest degree. It is easily implemented and is empirically known to give remarkable speedups over the trivial algorithm. We study the behavior of this algorithm over graphs with heavy-tailed degree distributions, a defining feature of real-world graphs. The erased configuration model (ECM) efficiently generates a graph with asymptotically (almost) any desired degree sequence. We show that the expected running time of this algorithm over the distribution of graphs created by the ECM is controlled by the @math -norm of the degree sequence. Norms of the degree sequence are a measure of the heaviness of the tail, and it is precisely this feature that allows non-trivial speedups of simple triangle enumeration algorithms. As a corollary of our main theorem, we prove expected linear-time performance for degree sequences following a power law with exponent @math , and non-trivial speedup whenever @math .
  @cite_18: Finding, counting and or listing triangles (three vertices with three edges) in massive graphs are natural fundamental problems, which have recently received much attention because of their importance in complex network analysis. Here we provide a detailed survey of proposed main-memory solutions to these problems, in a unified way. We note that previous authors have paid surprisingly little attention to space complexity of main-memory solutions, despite its both fundamental and practical interest. We therefore detail space complexities of known algorithms and discuss their implications. We also present new algorithms which are time optimal for triangle listing and beats previous algorithms concerning space needs. They have the additional advantage of performing better on power-law graphs, which we also detail. We finally show with an experimental study that these two algorithms perform very well in practice, allowing us to handle cases which were previously out of reach.
  @cite_22: We say an algorithm on n by n matrices with entries in [-M, M] (or n-node graphs with edge weights from [-M, M]) is truly sub cubic if it runs in O(n^ 3- ( M)) time for some > 0. We define a notion of sub cubic reducibility, and show that many important problems on graphs and matrices solvable in O(n^3) time are equivalent under sub cubic reductions. Namely, the following weighted problems either all have truly sub cubic algorithms, or none of them do: - The all-pairs shortest paths problem (APSP). - Detecting if a weighted graph has a triangle of negative total edge weight. - Listing up to n^ 2.99 negative triangles in an edge-weighted graph. - Finding a minimum weight cycle in a graph of non-negative edge weights. - The replacement paths problem in an edge-weighted digraph. - Finding the second shortest simple path between two nodes in an edge-weighted digraph. - Checking whether a given matrix defines a metric. - Verifying the correctness of a matrix product over the ( , +)-semiring. Therefore, if APSP cannot be solved in n^ 3- time for any > 0, then many other problems also need essentially cubic time. In fact we show generic equivalences between matrix products over a large class of algebraic structures used in optimization, verifying a matrix product over the same structure, and corresponding triangle detection problems over the structure. These equivalences simplify prior work on sub cubic algorithms for all-pairs path problems, since it now suffices to give appropriate sub cubic triangle detection algorithms. Other consequences of our work are new combinatorial approaches to Boolean matrix multiplication over the (OR, AND)-semiring (abbreviated as BMM). We show that practical advances in triangle detection would imply practical BMM algorithms, among other results. Building on our techniques, we give two new BMM algorithms: a derandomization of the recent combinatorial BMM algorithm of Bansal and Williams (FOCS'09), and an improved quantum algorithm for BMM.
  @cite_6: Abstract We consider the problem of orienting the edges of a planar graph in such a way that the out-degree of each vertex is minimized. If, for each vertex v , the out-degree is at most d , then we say that such an orientation is d -bounded. We prove the following results: • Each planar graph has a 5-bounded acyclic orientation, which can be constructed in linear time. • Each planar graph has a 3-bounded orientation, which can be constructed in linear time. • A 6-bounded acyclic orientation, and a 3-bounded orientation, of each planar graph can each be constructed in parallel time O(log n log ∗ n ) on an EREW PRAM, using O( n log n log ∗ n ) processors. As an application of these results, we present a data structure such that each entry in the adjacency matrix of a planar graph can be looked up in constant time. The data structure uses linear storage, and can be constructed in linear time.
  @cite_24: We present an assortment of methods for finding and counting simple cycles of a given length in directed and undirected graphs. Most of the bounds obtained depend solely on the number of edges in the graph in question, and not on the number of vertices. The bounds obtained improve upon various previously known results.
  @cite_23: Finding minimum circuits in graphs and digraphs is discussed. An almost minimum circuit is a circuit which may have only one edge more than the minimum. To find an almost minimum circuit an @math algorithm is presented. A direct algorithm for finding a minimum circuit has an @math behavior. It is refined to yield an @math average time algorithm. An alternative method is to reduce the problem of finding a minimum circuit to that of finding a triangle in an auxiliary graph. Three methods for finding a triangle in a graph are given. The first has an @math worst case bound ( @math for planar graphs); the second takes @math time on the average; the third has an @math worst case behavior. For digraphs, results of Bloniarz, Fisher and Meyer are used to obtain an algorithm with @math average behavior.
  @cite_13: 
summary: The idea of using some sort of degree binning, orienting edges, or thresholding for finding and enumerating triangles has been used in many results. Chiba and Nishizeki @cite_13 give bounds for a sequential version of using the degeneracy of a graph. This does not give bounds for , although their algorithm is similar in spirit. Alon, Yuster, and Zwick @cite_24 find triangles in @math using degree thresholding and matrix multiplication ideas from Itai and Rodeh @cite_23 . Chrobak and Eppstien @cite_6 use acyclic orientations for linear time triangle enumeration in planar graphs. Vassilevska Williams and Williams @cite_22 show that fast algorithms for weighted triangle enumeration leads to remarkable consequences, like faster all-pairs shortest paths. In the work most closely to ours, Latapy @cite_18 discusses various triangle finding algorithms, and also focuses on power-law graphs. He shows the trivial bound of @math when the power law exponent is @math . Essentially, the maximum degree is @math and that directly gives a bound on the number of @math s.