Please consider the following problem. It can (but probably shouldn't) be called offline version of online triangle detection on subgraphs.

Given a graph $G$ and a collection $C$ of subsets of nodes. One need to compute for each $S \in C$ the number of triangles in $G[S]$ - subgraph induced on $S$.

Do we know any efficient way to do this?

Clearly one can do it in $|C| n^{\omega}$. But I was hoping for something better.

The only relevant result I'm aware of is "Clustered integer 3SUM via additive combinatorics" by TM Chan and M Lewenstein. They were able to provide an algorithm with running time $O(n^{\frac{13}{7}} |C|)$ for sufficiently large $|C|$ for $3$-Sum in the same setting: given $n$ numbers and collection $C$ of subsets of this numbers, one needs to solve $3$-Sum on each subset.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.