The graph is generated with $p=n^{-0.5}$,which $p$ means the probability the two random vector dot product is large enough to add an edge. Brute force algorithm run in expect time $O(n^2)$.I think the expect number of 3-cycles are O(n).Is there an algorithm run in expect time in $O(m)$ or at least better than brute force?
Asked
Active
Viewed 51 times
1
-
Unless you're looking for an expected rather than worst-case time, the random graph model will not matter. (But do you mean random dot product graph?) What will matter is the input format; e.g. if the graph is given as an adjacency matrix, then obviously we cannot do better than $O(n^2)$. – Misha Lavrov Apr 10 '23 at 22:07
-
Sorry for my mistake, my meaning just as you says. – Hilbert Hugin Apr 10 '23 at 23:51
1 Answers
1
Finally , i get an negative result. This paper 1 shows that need at least $O(m^{4/3})$ time for a exact algorithm under ASPS hypothesis which is as bad as brute force.