8
$\begingroup$

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. 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.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ 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 ? $\endgroup$
    – Suresh Venkat
    Jan 29, 2012 at 17:34
  • 1
    $\begingroup$ 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 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). $\endgroup$
    – Shir
    Jan 30, 2012 at 7:34
  • 1
    $\begingroup$ So you want a sublinear algorithm that estimates the number of triangles ? $\endgroup$
    – Suresh Venkat
    Jan 30, 2012 at 21:27
  • 2
    $\begingroup$ 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? $\endgroup$
    – virgi
    Jan 30, 2012 at 21:27
  • 2
    $\begingroup$ 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. $\endgroup$
    – virgi
    Jan 30, 2012 at 21:37

3 Answers 3

Reset to default
9
$\begingroup$

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 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 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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ 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. :) $\endgroup$
    – Shir
    Jan 29, 2012 at 9:13
3
$\begingroup$

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.

Improve this answer
$\endgroup$
3
$\begingroup$

In the comments to David Eppstein's answer 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).

Improve this answer
$\endgroup$
6
  • $\begingroup$ WRT query complexity, see also "Quantum algorithms for the triangle problem", Magniez, Santha, and Szegedy, SODA'05 and arXiv:quant-ph/0310134. $\endgroup$
    – David Eppstein
    Jan 30, 2012 at 16:01
  • $\begingroup$ 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. $\endgroup$
    – Shir
    Jan 30, 2012 at 16:21
  • $\begingroup$ @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. $\endgroup$
    – Artem Kaznatcheev ♦
    Jan 30, 2012 at 19:07
  • $\begingroup$ 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. $\endgroup$
    – Artem Kaznatcheev ♦
    Jan 30, 2012 at 19:13
  • 1
    $\begingroup$ 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) $\endgroup$
    – Shir
    Jan 30, 2012 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.