<p>For several references for the problem of testing for the existence of a triangle (exactly, not in the property testing framework), see <a href="http://en.wikipedia.org/wiki/Triangle-free_graph#Triangle_finding_problem">Triangle-free graph</a> on Wikipedia. In particular Alon, Yuster, and Zwick (ESA'94) give an O(m^{1.41}) algorithm, and it can also be done in fast matrix multiplication time which is better for dense graphs.</p>

<p>If you're ok with something in the dynamic graph algorithms setting, I also have one for counting the triangles: </p>

<p>The h-index of a graph and its application to dynamic subgraph statistics, D. Eppstein and E. S. Spiro, <a href="http://arxiv.org/abs/0904.3741">arXiv:0904.3741</a> and WADS 2009.</p>

<p>In our paper we cite Chiba and Nishizeki (SICOMP 1985) and Itai and Rodeh (SICOMP 1978) for the basic static-algorithm facts that a graph with m edges can have at most O(m^{3/2}) triangles in the worst case and that they can be listed in that amount of time.</p>

CC BY-SA 3.0
2012-01-29T09:13:38.707Z
Thanks for the quick reply. I see now that I wasn't clear in my question as to exactly what we're looking for. I naturally saw the references in Wikipedia, but they don't quite fit, as I'm looking for something in the domain of query complexity, or running time for some probabilistic algorithm. I'll edit the question to reflect that. So vote up for the answer, but I won't accept it, as I'm still looking for an answer. :)
Shir
CC BY-SA 3.0
2012-01-29T08:59:19.507Z
2012-01-29T08:59:19.507Z
David Eppstein
<p>In the comments to <a href="https://cstheory.stackexchange.com/questions/9972/finding-triangles-in-a-graph-other-approaches-besides-property-testing/9973#9973">David Eppstein's answer</a> you ask for the domain of query complexity. I think what you describe has no papers written on it, because it has a trivial (deterministic, or randomized) query complexity lower bound of $\Omega(n^2)$ (where $n$ is the number of vertexes, so $O(n^2)$ is input size, and thus max query complexity). </p>

<hr>

<p>If you want to see why, consider the following graph family: </p>

<p>Define a graph $G_{0}$ as: there is a special vertex $v$, and two partitions $X$ and $Y$ of size $(n - 1)/2$. There is an edges between each vertex in $X$ and $v$ and between each vertex in $Y$ and $v$. </p>

<p>For $i \in X$ and $j \in Y$ define a graph $G_{ij}$ as $G_0$ with the edge $ij$ added.</p>

<p>$G_0$ has not triangles, and each $G_{ij}$ has 1 triangle. Given the promise that you graphs is either $G_0$ or $G_{ij}$ for some $i$ and $j$ is obviously equivalent to unordered search on $(n - 1)^2/4$ objects (the edges).</p>

CC BY-SA 3.0
2012-01-30T16:01:28.993Z
WRT query complexity, see also "Quantum algorithms for the triangle problem", Magniez, Santha, and Szegedy, SODA'05 and arXiv:quant-ph/0310134.
David Eppstein
CC BY-SA 3.0
2012-01-30T16:21:53.203Z
Your example only shows that for the case of a single triangle (I guess it generalizes to O(1) easily), it doesn't characterize the trade-off between the number of triangles and the probability of hitting one, or hint towards a good sampling strategy.
Shir
CC BY-SA 3.0
2012-01-30T19:07:15.913Z
@Shir my examples sets a lower bound via a partial function. Since any procedure for solving the triangle problem you described, has to also solve my partial function, the lower bound continues to hold. I.e. the question has no papers because it is obvious that solving it required $\Theta(n^2)$ queries.
Artem Kaznatcheev
CC BY-SA 3.0
2012-01-30T19:13:39.310Z
Note that as @DavidEppstein pointed out, the question was interesting in quantum query complexity since my above argument would only give a $\Omega(n)$ lower bound for quantum query complexity (for the same reason as it only give $\Omega(\sqrt{N})$ for unordered search. But you seem to be interested in deterministic and randomized query complexity.
Artem Kaznatcheev
CC BY-SA 3.0
2012-01-30T19:40:49.327Z
Not sure what you mean by lower bound via partial function. Also, I don't see why every procedure has to solve your example. How does your example disprove the existence of an algorithm that, provided that there are at least $n$ triangles in the graph, finds one with probability $1-1/\sqrt{n}$ using $\sqrt{n}$ queries? (the numbers here are completely arbitrary, I'm just trying to understand the point you are making)
Shir
CC BY-SA 3.0
2012-01-30T20:05:20.617Z
For randomized query complexity, we usually want things with constant (> 1/2) probability of success. But I agree that I did not consider the case of worrying about the parametric complexity where you express the complexity as some $f(n,k)$ where $n$ vertexes and $k$ of some other property like demanding that you have $k$ triangles.
Artem Kaznatcheev
CC BY-SA 3.0
2012-01-30T13:13:35.100Z
2012-01-30T13:19:09.370Z
2017-04-13T12:32:28.077Z
Artem Kaznatcheev
<p>I don't exactly understand your question in terms of your final objective. However, you could consider the FPT version of the triangle packing problem, if that helps in someway in your problem. In particular, you could consider Edge Disjoint Triangle Packing(EDTP) or Vertex Disjoint Triangle Packing(VDTP) and kernelize the instance of the graph to O(k) or O(k^2) respectively in terms of number of vertices. You could also kernelize on the number of triangles [O(k^3)]. After kernelization, it would be easier to analyse the triangles in the graph instance.</p>

CC BY-SA 3.0
2012-01-29T20:57:48.837Z
2012-01-29T20:57:48.837Z
Nikhil
<p>We're working on a paper that presents some algorithms for finding triangles and network motifs (constant size subgraphs, also known as graphlets) in a distributed setting. We characterize the tradeoff between the number of triangles in the graph and the communication load necessary. I am looking for references to work done on this question in the centralized model. </p>

<p>The problem is that nearly everything I found on this topic that had a theoretical flavor to it was within the framework of <a href="http://en.wikipedia.org/wiki/Property_testing">property testing</a>. To illustrate the difference - consider the case of a graph with $n$ vertices, that is comprised of $n-2$ triangles all sharing the edge $\left(1,2\right)$. From the point of view of property testing, this graph is very close to be triangle-free (removing that critical edge does the job), whereas it has a linear number of triangles, which is a lot by our standards.</p>

<p>Any references at all will be appreciated.</p>

<p><strong>Edit:</strong> I'm mainly interested in algorithms that can determine whether the graph contains triangles quickly. For triangle (or other subgraph) listing algorithms, the running time is naturally bounded from below by the number of triangles in the graph, as the algorithm needs to list them all, making such instances harder in a sense. From the point of view of a decision problem ("triangle-free or not"), having many triangles actually makes the problem easier, since you can easily find one.</p>

CC BY-SA 3.0
2012-01-29T17:34:15.580Z
Given David's response, I'm not sure I understand any more what you want. You don't like the property testing framework, but you want query complexity bounds ?  Is the example you give in the question a bad case because you want to estimate the *number* of triangles as well ?
Suresh Venkat
CC BY-SA 3.0
2012-01-30T07:34:56.600Z
Here's what I want - a probabilistic algorithm, that queries the graph, and is able and distinguish between graphs with many triangles to graphs with none. See for instance http://dl.acm.org/citation.cfm?id=1873611 by Gonen, Ron and Shavit. However, in their paper the query is restricted (for instance, if I understand correctly, edge queries are not allowed, unless sampled from a uniform distribution).
Shir
CC BY-SA 3.0
2012-01-30T21:27:37.083Z
So you want a sublinear algorithm that estimates the number of triangles ?
Suresh Venkat
CC BY-SA 3.0
2012-01-30T21:27:56.410Z
some simple observations: say you have T triangles and you are allowed randomization; then you can sample: (1) an edge and you'll hit a triangle with probability at least ~T^{2/3}/m since the min number of edges you can have in a graph with T triangles is ~T^{2/3}; once you have an edge, you can check if it is in a triangle in n steps, so you get an algorithm of expected runtime ~mn/T^{2/3}; (2) you can pick a random triple of vertices and with probability T/n^3 it will be a triangle so this gives you a runtime of ~n^3/T. You can also do some slightly more sophisticated things. Does this help?
virgi
CC BY-SA 3.0
2012-01-30T21:37:47.257Z
Oh, and also, any algorithm which can detect whether a given graph contains a triangle in ~n^{3-eps} time can be converted into one which can multiply nxn Boolean matrices in ~n^{3-eps/3} time, so nice simple triangle detection algorithms are of interest for this reason as well, though of course the hard instances are when you need to distinguish between the cases of 0 or 1 triangle, and for this case we don't know anything better than computing the cube of the adjacency matrix.
virgi
CC BY-SA 3.0
2012-01-30T22:11:23.887Z
@virgi, this is indeed the type of arguments I was looking for, but the observations you presented are naturally stuff we came up with quite early and are rather simple. My question was aimed at more concrete strategies, say, based on the degree distribution, if it is given, and so on.
Shir
CC BY-SA 3.0
2012-01-31T01:34:30.240Z
here's a slightly improved argument if you are allowed to use fast matrix multiplication: say nxn matrix mult can be done in n^w time, then sample a subset S of the nodes of size s; the expected number of triangles you hit is roughly (s/n)^3 T which is at least 1 when s=n/T^{1/3}; so then use matrix mult to find a triangle in S and you'll get a runtime of ~n^w/T^{w/3}; of course, repeat to boost your probability. What type of a result would you like in terms of a given degree distribution?
virgi
CC BY-SA 3.0
2012-01-31T05:33:05.213Z
@virgi, that's nice but I was looking mostly for references. Thanks though.
Shir
<reference-request><graph-theory><graph-algorithms>
Finding triangles in a graph: other approaches besides property testing?
Shir
# Finding triangles in a graph: other approaches besides property testing?

(Asked by: username_0 on 2012-01-29)

We're working on a paper that presents some algorithms for finding triangles and network motifs (constant size subgraphs, also known as graphlets) in a distributed setting. We characterize the tradeoff between the number of triangles in the graph and the communication load necessary. I am looking for references to work done on this question in the centralized model.

The problem is that nearly everything I found on this topic that had a theoretical flavor to it was within the framework of [property testing](http://en.wikipedia.org/wiki/Property_testing). To illustrate the difference - consider the case of a graph with $n$ vertices, that is comprised of $n-2$ triangles all sharing the edge $\left(1,2\right)$. From the point of view of property testing, this graph is very close to be triangle-free (removing that critical edge does the job), whereas it has a linear number of triangles, which is a lot by our standards.

Any references at all will be appreciated.

**Edit:** I'm mainly interested in algorithms that can determine whether the graph contains triangles quickly. For triangle (or other subgraph) listing algorithms, the running time is naturally bounded from below by the number of triangles in the graph, as the algorithm needs to list them all, making such instances harder in a sense. From the point of view of a decision problem ("triangle-free or not"), having many triangles actually makes the problem easier, since you can easily find one.

**Tags:** reference-request, graph-theory, graph-algorithms
> **Comments:**
> **username_1**: Given David's response, I'm not sure I understand any more what you want. You don't like the property testing framework, but you want query complexity bounds ?  Is the example you give in the question a bad case because you want to estimate the *number* of triangles as well ?  
> **username_0**: Here's what I want - a probabilistic algorithm, that queries the graph, and is able and distinguish between graphs with many triangles to graphs with none. See for instance http://dl.acm.org/citation.cfm?id=1873611 by Gonen, Ron and Shavit. However, in their paper the query is restricted (for instance, if I understand correctly, edge queries are not allowed, unless sampled from a uniform distribution).  
> **username_1**: So you want a sublinear algorithm that estimates the number of triangles ?  
> **username_2**: some simple observations: say you have T triangles and you are allowed randomization; then you can sample: (1) an edge and you'll hit a triangle with probability at least ~T^{2/3}/m since the min number of edges you can have in a graph with T triangles is ~T^{2/3}; once you have an edge, you can check if it is in a triangle in n steps, so you get an algorithm of expected runtime ~mn/T^{2/3}; (2) you can pick a random triple of vertices and with probability T/n^3 it will be a triangle so this gives you a runtime of ~n^3/T. You can also do some slightly more sophisticated things. Does this help?  
> **username_2**: Oh, and also, any algorithm which can detect whether a given graph contains a triangle in ~n^{3-eps} time can be converted into one which can multiply nxn Boolean matrices in ~n^{3-eps/3} time, so nice simple triangle detection algorithms are of interest for this reason as well, though of course the hard instances are when you need to distinguish between the cases of 0 or 1 triangle, and for this case we don't know anything better than computing the cube of the adjacency matrix.  
> **username_0**: @virgi, this is indeed the type of arguments I was looking for, but the observations you presented are naturally stuff we came up with quite early and are rather simple. My question was aimed at more concrete strategies, say, based on the degree distribution, if it is given, and so on.  
> **username_2**: here's a slightly improved argument if you are allowed to use fast matrix multiplication: say nxn matrix mult can be done in n^w time, then sample a subset S of the nodes of size s; the expected number of triangles you hit is roughly (s/n)^3 T which is at least 1 when s=n/T^{1/3}; so then use matrix mult to find a triangle in S and you'll get a runtime of ~n^w/T^{w/3}; of course, repeat to boost your probability. What type of a result would you like in terms of a given degree distribution?  
> **username_0**: @virgi, that's nice but I was looking mostly for references. Thanks though.  

---

## 3 answers

### Answer by username_3 on 2012-01-29. Score: 9

For several references for the problem of testing for the existence of a triangle (exactly, not in the property testing framework), see [Triangle-free graph](http://en.wikipedia.org/wiki/Triangle-free_graph#Triangle_finding_problem) on Wikipedia. In particular Alon, Yuster, and Zwick (ESA'94) give an O(m^{1.41}) algorithm, and it can also be done in fast matrix multiplication time which is better for dense graphs.

If you're ok with something in the dynamic graph algorithms setting, I also have one for counting the triangles:

The h-index of a graph and its application to dynamic subgraph statistics, D. Eppstein and E. S. Spiro, [arXiv:0904.3741](http://arxiv.org/abs/0904.3741) and WADS 2009.

In our paper we cite Chiba and Nishizeki (SICOMP 1985) and Itai and Rodeh (SICOMP 1978) for the basic static-algorithm facts that a graph with m edges can have at most O(m^{3/2}) triangles in the worst case and that they can be listed in that amount of time.

> **Comments:**
> **username_0**: Thanks for the quick reply. I see now that I wasn't clear in my question as to exactly what we're looking for. I naturally saw the references in Wikipedia, but they don't quite fit, as I'm looking for something in the domain of query complexity, or running time for some probabilistic algorithm. I'll edit the question to reflect that. So vote up for the answer, but I won't accept it, as I'm still looking for an answer. :)  

---

### Answer by username_4 on 2012-01-30. Score: 3

In the comments to [David Eppstein's answer](https://cstheory.stackexchange.com/questions/9972/finding-triangles-in-a-graph-other-approaches-besides-property-testing/9973#9973) you ask for the domain of query complexity. I think what you describe has no papers written on it, because it has a trivial (deterministic, or randomized) query complexity lower bound of $\Omega(n^2)$ (where $n$ is the number of vertexes, so $O(n^2)$ is input size, and thus max query complexity).

---

If you want to see why, consider the following graph family:

Define a graph $G\_{0}$ as: there is a special vertex $v$, and two partitions $X$ and $Y$ of size $(n - 1)/2$. There is an edges between each vertex in $X$ and $v$ and between each vertex in $Y$ and $v$.

For $i \in X$ and $j \in Y$ define a graph $G\_{ij}$ as $G\_0$ with the edge $ij$ added.

$G\_0$ has not triangles, and each $G\_{ij}$ has 1 triangle. Given the promise that you graphs is either $G\_0$ or $G\_{ij}$ for some $i$ and $j$ is obviously equivalent to unordered search on $(n - 1)^2/4$ objects (the edges).

> **Comments:**
> **username_3**: WRT query complexity, see also "Quantum algorithms for the triangle problem", Magniez, Santha, and Szegedy, SODA'05 and arXiv:quant-ph/0310134.  
> **username_0**: Your example only shows that for the case of a single triangle (I guess it generalizes to O(1) easily), it doesn't characterize the trade-off between the number of triangles and the probability of hitting one, or hint towards a good sampling strategy.  
> **username_4**: @Shir my examples sets a lower bound via a partial function. Since any procedure for solving the triangle problem you described, has to also solve my partial function, the lower bound continues to hold. I.e. the question has no papers because it is obvious that solving it required $\Theta(n^2)$ queries.  
> **username_4**: Note that as @DavidEppstein pointed out, the question was interesting in quantum query complexity since my above argument would only give a $\Omega(n)$ lower bound for quantum query complexity (for the same reason as it only give $\Omega(\sqrt{N})$ for unordered search. But you seem to be interested in deterministic and randomized query complexity.  
> **username_0**: Not sure what you mean by lower bound via partial function. Also, I don't see why every procedure has to solve your example. How does your example disprove the existence of an algorithm that, provided that there are at least $n$ triangles in the graph, finds one with probability $1-1/\sqrt{n}$ using $\sqrt{n}$ queries? (the numbers here are completely arbitrary, I'm just trying to understand the point you are making)  
> **username_4**: For randomized query complexity, we usually want things with constant (> 1/2) probability of success. But I agree that I did not consider the case of worrying about the parametric complexity where you express the complexity as some $f(n,k)$ where $n$ vertexes and $k$ of some other property like demanding that you have $k$ triangles.  

---

### Answer by username_5 on 2012-01-29. Score: 3

I don't exactly understand your question in terms of your final objective. However, you could consider the FPT version of the triangle packing problem, if that helps in someway in your problem. In particular, you could consider Edge Disjoint Triangle Packing(EDTP) or Vertex Disjoint Triangle Packing(VDTP) and kernelize the instance of the graph to O(k) or O(k^2) respectively in terms of number of vertices. You could also kernelize on the number of triangles [O(k^3)]. After kernelization, it would be easier to analyse the triangles in the graph instance.


---

