Triangle Detection in $𝑯$-Free Graphs

On the lower bound side, we identify two classes of patterns for which, under Conjecture 1, there is no strongly subcubic Triangle Detection algorithm for $H$-free graphs. Formally, we prove the following theorem using standard self-reductions in this branch of research.

On the upper bound side, we employ three different techniques to solve the problem for different classes of patterns, putting us close to proving a dichotomy theorem: a complete classification of patterns into those for which Triangle Detection in $H$-free graphs is strongly subcubic, and those for which a conditional lower bound of $n^{3-o(1)}$ exists.

Before we present the results, let us build some intuition. Our starting point is bipartite patterns. Suppose $H$ is a bipartite graph with parts of sizes $s\le t$. By the Kovári-Sós-Turán theorem [33] (abbreviated as KST), an $H$-free graph $G$ contains at most $O(n^{2-1/s})$ edges, so the problem can be solved trivially in $O(n^{3-1/s})$ time.

For non-bipartite graphs, the smallest case is $H=K_3$, which is trivial: If $G$ is triangle-free, an algorithm can answer NO in constant time. Another simple case is when $H$ is a triangle with an attached edge. In an $H$-free graph, any vertex of a triangle cannot have a neighbor outside that triangle. This implies that the vertices of a triangle in $G$ have degree $2$. Therefore, one can find a triangle in $O(m+n)$ time by processing only the vertices of degree $2$. The smallest non-trivial case is when $H$ is a cycle of length $5$, denoted by $C_5$. Our starting point is a combinatorial and strongly subcubic Triangle Detection algorithm for $C_5$-free graphs.

In later sections, we will see that this algorithm is not optimal; however, it serves as an important warm-up because it utilizes many of the core ideas in our most general results. Specifically, the approach is to try to embed the forbidden pattern randomly in the graph $G$. The randomness ensures that a triangle that is incident to a high-degree vertex is contained in the area surrounding the embedded pattern. Eventually, we gain a speed-up by restricting the search to an area that, on the one hand, contains a triangle edge. On the other hand, every non-triangle edge in it completes the embedding of the forbidden pattern. Essentially, the problem is reduced to deciding if there is an edge in a subgraph of $G$.

By generalizing this embedding approach, we provide an algorithm that applies to more patterns. It turns out that there is a large and rich family of patterns that can be embedded in worst-case Triangle Detection graphs, resulting in a polynomial speed-up. These embeddable patterns are characterized by admitting a special type of $3$-coloring, defined as follows.

For patterns that admit a nice coloring, we provide the following result.

An immediate question that arises is about the generality of this result, i.e., which patterns admit a nice coloring. Let us begin by showing that it captures the most basic cases already discussed. First, observe that all bipartite graphs admit a nice coloring, because every neighborhood in a proper $2$-coloring must be monochromatic. A triangle clearly admits a nice coloring. Next, observe that every cycle of odd length greater than $3$ admits a nice coloring, e.g., by coloring it greedily with two colors until the process is stuck at the last vertex, which gets a third color. The reason this coloring is nice is that the second vertex to receive a color will have a monochromatic neighborhood. After removing it, the remaining pattern is a path, and its endpoints must also have a monochromatic neighborhood. As an immediate consequence, we also get that all patterns which are $C_k$-colorable¹¹1A graph $G$ is $H$-colorable if there is a homomorphism from $G$ to $H$. Equivalently, it means that $G$ is a subgraph of a blowup of $H$, i.e., the graph obtained by replacing every edge of $H$ with a biclique. for some $k>3$ admit a nice coloring, as the greedy coloring can also nicely color the color classes in a $C_k$-colored pattern. However, the result is even more general than $C_k$-colored patterns: For example, the smallest triangle-free patterns that are not $C_5$-colorable have $8$ vertices [23, Theorem 1.1, Figure 3]. The graph in Figure 1 is such a pattern, yet it also admits a nice coloring that we illustrate in the figure.

Perhaps every pattern $H$ which does not fall in the lower bound classes of Theorem 2 admits a nice coloring? From a local view, it seems plausible: If $H$ is $3$-colorable and contains at most one triangle, then the neighborhoods of non-triangle vertices are independent sets. Thus, these neighborhoods can be properly colored with only one color. A similar notion of colorings, called adynamic colorings, was studied by Šurimová et al. [34]. This paper refutes that idea by giving an example of a triangle-free, $3$-colorable graph $H$, such that every proper $3$-coloring of $H$ does not admit a vertex with a monochromatic neighborhood. Specifically, $H$ consists of two copies of a $6$-cycle such that each vertex in the first copy is connected to two vertices in the second copy: to its copy and to the antipodal vertex of its copy. See Figure 2.

A curious observation that we make is that cycles of length divisible by $3$ are inherent in such examples. In particular, if a $3$-colorable graph is free from such cycles, then not only does it admit a nice coloring, but every proper $3$-coloring is nice.

Understanding these examples is crucial to our goal of proving a dichotomy theorem. It could be that the missing component for such a theorem is a lower bound for patterns that do not admit a nice coloring. It turns out that the story does not end here, as there are patterns $H$ which do not admit a nice coloring, yet $H$-free graphs admit a strongly subcubic combinatorial Triangle Detection algorithm.

Our next family of patterns for which we show a strongly subcubic algorithm is a generalization to patterns that are essentially characterized by a single triangle being the only obstacle to a nice coloring.

Together, our results provide a complete picture for small patterns.

We also suggest a minimal example of a pattern $H$ that does not fall into any of the four categories. The pattern is constructed similarly to the one in Figure 2, but we replace one of the $6$-cycles with a triangle. See Figure 3.

Another set of results we provide addresses Open 2 about $H$-sensitive algorithms. These are algorithms that run faster when the number of copies of a pattern $H$ is polynomially smaller than the maximum possible, which can be as high as $\mathrm{\Omega }(n^k)$. $H$-sensitive algorithms are desirable because their complexity improves upon the worst-case complexity of the problem (i.e., they are never slower). In particular, an $H$-sensitive algorithm demonstrates that the hardest instances of Triangle Detection contain a maximum number of copies of $H$, aligning with the idea that pseudorandom graphs are the most challenging. We provide a generalization of the algorithm from Theorem 5 to an $H$-sensitive algorithm for every $H$ that admits a nice coloring.

Note that the distinction between triangle-free patterns and those that contain a triangle is necessary: By Theorem 2, there exist worst-case Triangle Detection instances with only one triangle, and consequently, only $O(n^{k-3})$ copies of $H$ for every pattern $H$ that contains a triangle, as opposed to potentially $\mathrm{\Omega }(n^k)$ copies in the triangle-free case. Therefore, an $H$-sensitive algorithm for a pattern $H$ that contains a triangle should run in cubic time when $t=\mathrm{\Omega }(n^{k-3})$, whereas if $H$ is triangle-free, then the running time for the same value of $t$ should be strongly subcubic.

We also remark that the algorithm requires an upper bound $t$ on the number of copies of $H$ as input. This assumption slightly weakens the result, but it can be removed easily in the case where $H$ is triangle-free by computing an (not necessarily tight) upper bound on the number of copies of $H$ during a preprocessing step, which still yields a strongly subcubic algorithm if $G$ has polynomially fewer than $n^k$ copies of $H$.²²2For example, consider a triangle-free pattern $H$. Suppose that we take $\mathrm{\Theta }(n^2\log n)$ samples of $k$-tuples of vertices, and for each tuple we check if it induces a copy of $H$. If the first copy of $H$ was found after $\mathrm{\Omega }(n^{\alpha }\log n)$ samples, for any , we conclude that $t\le n^{k-\alpha }$ with high probability. If no copy appears in $\mathrm{\Theta }(n^2\log n)$ samples, we conclude that $t\le n^{k-2}$. We note that if $H$ contains a triangle, then it is necessary for an $H$-sensitive algorithm to receive $t$ as an input, under Conjecture 1: If there was an $H$-sensitive Triangle Detection algorithm that is oblivious to the upper bound $t$, then it would need to run in subcubic time on every triangle-free graph $G$ (as then $t=0$). Using such an algorithm, we can distinguish triangle-free graphs from graphs that contain a triangle by running the supposed algorithm and answering YES if its running time exceeds the stated bound when $t=0$.

Additionally, we provide a more efficient algorithm for the special case of $H=C_5$.

Note that, unlike the previous algorithm, this one is oblivious to $t$.

Cycles (using $C_k$ to denote the cycle of length $k$) are one of the most natural classes of graphs, so a natural question is about the running time of Triangle Detection in $C_k$-free graphs, for each $k$. For the case of even cycles, $C_{2k}$ is bipartite, so the KST theorem can be employed to get an $O(n^{3-1/k})$ time algorithm. In fact, it is possible to do much better than that, because not only is the graph sparse, it follows from the Bondy-Simonovits theorem that a $C_{2k}$-free graph is $d$-degenerate for $d=O(n^{1/k})$ [13]. A graph is $d$-degenerate if every induced subgraph contains a vertex of degree less than $d$. The classic Chiba-Nishizeki algorithm solves Triangle Detection in $d$-degenerate graphs in $O(md)=O(n^{1+2/k})$ time [17].³³3The original paper uses arboricity rather than degeneracy, but the two parameters are known to differ by at most a factor of two. For odd cycles, the problem is more complex, as illustrated by complete bipartite graphs, which are $C_{2k+1}$-free but also very dense. We overcome this challenge by essentially restricting the search to graphs that have the form of a dense bipartite graph with a bounded degeneracy graph added to one of its parts. This requires a generalization of the Chiba-Nishizeki algorithm to graphs that are only partially degenerate. In addition, we employ a novel idea, an algorithmic adaptation of a supersaturation result for even cycles by Jiang and Yepremyan [27]. Together, we manage to prove the following theorem.

Note that this running time matches the bound for $C_{2k}$-free graphs (using Chiba-Nishizeki), up to an additive $m$ term.

A summary of the results so far is presented in Table 1.

A related line of work has considered the purely combinatorial question of bounding the number of triangles in $H$-free graphs. This Turán-type question was initiated in a paper by Alon and Shikhelman [8], and since its introduction, many papers on the subject have appeared (see [22] for a recent survey). For every pattern $H$, let $ex(K_3,H)$ be the maximum number of triangles in an $n$-vertex $H$-free graph. An analogous result to our first lower bound class in Theorem 2 follows from [8, Proposition 2.1] and shows that $ex(K_3,H)$ is strongly subcubic if and only if $H$ is $3$-colorable. One might wonder if the proof is algorithmic, in the sense that it also provides an efficient way to find the triangles if $H$ is $3$-colorable. However, an algorithmic proof of this result cannot hold generally for all $3$-colorable patterns. That is because there are patterns that are $3$-colorable but do not admit a strongly subcubic combinatorial Triangle Detection algorithm under Conjecture 1. For example, if $H$ is the diamond graph (two triangles that share an edge), then clearly $ex(K_3,H)=O(n^2)$, whereas Theorem 2 shows that Triangle Detection in diamond-free graphs requires $n^{3-o(1)}$ time under Conjecture 1. In the opposite direction, the algorithmic question may contribute to the mathematical one, as a combinatorial Triangle Detection algorithm for $H$-free graphs offers insight into the structure of triangles in $H$-free graphs, which may be used to prove upper bounds on $ex(K_3,H)$.

A more relatable variant of Triangle Detection is the Triangle Listing problem, in which the goal is to produce a list of all the triangles in a graph. This problem generalizes not only Triangle Detection but also its weighted variants, such as Negative Triangle (an APSP-hard problem [38]) and $0$-Triangle (a 3SUM-hard problem [37]). A primary objective in designing a listing algorithm is to ensure it is output-sensitive, meaning the running time is proportional to the number of triangles in the graph. Ideally, the running time should match the running time for detection when the output size is small and scale up to $\mathrm{\Theta }(n^3)$ when the number of triangles reaches its maximum of $\mathrm{\Omega }(n^3)$ (see e.g., [11]). The problem of combinatorial Triangle Listing for general graphs is straightforward, as the trivial $O(n^3)$ time algorithm for detection can also list all the triangles in the same running time and is tight under Conjecture 1. In the setting of $H$-free graphs, the situation is less clear. Our lower bounds for detection in Theorem 2 clearly hold for listing as well. For $H$ that does not fall into a lower bound class, the trivial $O(n^3)$ time listing algorithm seems wasteful because the output size is at most $ex(K_3,H)$, which is strongly subcubic by [8, Proposition 2.1] (as $H$ is $3$-colorable).

A general upper bound on $ex(K_3,H)$ that applies to every $3$-colorable $H$ is given by plugging a KST-type theorem for $3$-uniform hypergraphs [40, Theorem 1.5.7] into the proof of [8, Proposition 2.1], resulting in $ex(K_3,H)=O(n^{3-1/k^2})$. For the special case where $H=C_{2k+1}$, it is established that $ex(K_3,C_{2k+1})=O(ex(K_2,C_{2k}))$ [25], where $ex(K_2,C_{2k})$ is the maximum number of edges in a $C_{2k}$-free graph, bounded by $O(n^{1+1/k})$ [13]. A general lower bound by Kostochka et al. [32] shows that for every $3$-colorable $H$, $ex(K_3,H)=\mathrm{\Omega }(n^{3-\frac{3k-9}{e(H)-3}})$, where $e(H)$ is the number of edges in $H$. In particular, for dense $3$-colorable patterns we get $ex(K_3,H)=n^{3-O(1/k)}$. This gives a lower bound on the running time for listing, as the output size can be as large as $ex(K_3,H)$.

Our Triangle Detection algorithms for $H$-free graphs generalize well to the listing setting, producing a list of all triangles in the same time it takes to detect a single one. The running time is independent of the output size because, as discussed, the output size in $H$-free graphs is bounded by $O(n^{3-1/k^2})$ (or $O(n^{1+1/k})$ if $H=C_{2k+1}$), whereas our algorithms run slower.

In the case of nicely colored patterns, we observe a significant gap between $ex(K_3,H)=O(n^{3-1/k^2})$ and the stated running time. It is an interesting question whether the exponential dependence in our running time could be replaced by, e.g., a polynomial dependence $O(n^{3-1/k^{O(1)}})$. In the case of odd cycles, we see a smaller gap, a factor roughly $n^{1/k}$ between the combinatorial bound and the algorithmic running time. It seems likely that some algorithmic overhead is necessary for finding the triangles, even in $C_{2k+1}$-free graphs.

We begin with a simple $\tilde{O}(n^{7/3})$-time algorithm for $C_5$-free graphs, demonstrating the techniques and proving Proposition 3.

It is possible to generalize the embedding algorithm to be $H$-sensitive by employing the following idea: In a sample of $\tilde{O}(n/\mathrm{\Delta })$ vertices in a graph with high-minimum degree and at most $t$ copies of $H$, one of the sampled vertices is an $H$-light neighbor of the triangle with high probability. That is, a neighbor of the triangle that participates in at most $O(t/\mathrm{\Delta })$ copies of $H$. This ensures that the number of copies of the forbidden pattern reduces by a factor of $\mathrm{\Delta }$ at each step. When a base case is reached, the number of copies of a very basic pattern (e.g., a single vertex) is small enough for the base case to be solved efficiently. For instance, if the number of vertices of a certain color is small, triangles incident to them can be found quickly.

Let us now explain the high-level overview of the algorithm for $C_{2k+1}$-free graphs. Unlike the previous algorithms, this one is deterministic and employs a significantly different approach. The idea is to process the layers of a $k$-hop ball around a vertex as long as the layers are expanding. The algorithm searches for triangles in the first $k-1$ layers using a generalized Chiba-Nishizeki algorithm. If a triangle is not found, then most of the ball is deleted (except for the last two layers, which may still contain a triangle), ensuring a bounded number of phases before we run out of vertices. This approach exploits the structure of $C_{2k+1}$-free graphs using three main components:

• $\mathrm{■}$

  A lemma stating that the subgraph induced by any single layer in the ball is $O(k)$-degenerate.

• $\mathrm{■}$

  A generalization of the Chiba-Nishizeki algorithm that can find triangles with at least one edge in a specified $O(k)$-degenerate subgraph. This algorithm is useful for finding a triangle with an edge that lies within a layer.

• $\mathrm{■}$

  An efficient algorithm that identifies a large fraction of edges between the last two layers of the ball that participate in a $2k$-cycle, and for each such edge, it finds a $2k$-cycle containing it.

The last component is crucial: An edge that participates in a $2k$-cycle cannot form a triangle with a vertex outside that cycle without creating a $(2k+1)$-cycle. Thus, to check such an edge for triangles, one only needs to inspect the adjacencies to the other $2k-2$ vertices of a known $2k$-cycle containing it, which takes $O(k)=O(1)$ time.

A large body of research is devoted to proving dichotomy theorems for $H$-free graphs: showing a separation between patterns for which a problem is “hard” in $H$-free graphs and patterns for which the problem becomes “easy”. The precise definitions of hard and easy may vary, but most of this research uses coarse notions of hardness, such as NP-completeness versus polynomial-time. For example, such theorems have been proven for Max-Cut, Maximum Independent Set, and List-Coloring [30, 6, 24]. An almost complete dichotomy also exists for Subgraph Isomorphism [12].

Interestingly, a comprehensive work by Johnson et al. [29] provided a meta-theorem that captures many problems for which such a dichotomy exists, using a framework applicable in different complexity regimes. Roughly speaking, the meta-theorem states that if a problem (e.g., Maximum Independent Set) is easy on bounded-treewidth graphs, hard on subcubic graphs (graphs of degree at most $3$), and hard on edge subdivisions of subcubic graphs, then a complete dichotomy exists between patterns for which the problem is easy and patterns for which it is hard in $H$-free graphs. Their framework is applied to various problems, primarily in the coarse complexity regimes. However, the paper also demonstrates its generality by applying it to problems in $P$. Namely, they consider the Diameter and Radius problems, showing a separation between patterns for which the problem is solvable in near-linear time and patterns for which the problem does not admit a strongly subquadratic algorithm.

Our work uses the hard and easy notions of cubic and strongly subcubic time, respectively. Under these notions, Triangle Detection does not fall into their framework because the problem is solvable in linear time on subcubic graphs, which makes it easy. One may wonder about the status of the NP-complete and parameterized generalizations of Triangle Detection, i.e., Maximum Clique and $k$-Clique. For Maximum Clique, the problem in $H$-free graphs is trivially solvable in polynomial time for any fixed $H$, as the largest clique in an $H$-free graph has size less than $|H|$. For $k$-Clique, one could seek an FPT/W[1] dichotomy between patterns. This problem is interesting only when $|H|>k$, but it appears not to have been considered in the literature yet.