5
$\begingroup$

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.

$\endgroup$

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.