2

I got asked this in an interview and was told that O(n^2) is possible. Anyone has a simple approach for that?

Found here a paper telling me that it is as hard as matrix multiplication: http://kam.mff.cuni.cz/~matousek/cla/tria-mmult.pdf

Amtrix
  • 338
  • 2
  • 10
  • I promptly offered an O(n^3) with possible optimizations. One of them was using bitmasks for the set intersections -- still leading to O(n^3) with a constant boost. – Amtrix May 19 '15 at 03:25
  • 1
    Did the graph have any other properties? e.g. a counting triangles in a planar graph is only O(n). – Peter de Rivaz May 19 '15 at 06:14
  • No more information was given regarding the graph type. – Amtrix May 19 '15 at 21:17

2 Answers2

0

http://en.wikipedia.org/wiki/Triangle-free_graph

Testing if a graph is triangle-free would be solved by a solution for that problem. O(n^2) should have been a mistake from the interviewers' side.

Amtrix
  • 338
  • 2
  • 10
  • Yes, they're either confused or testing you. – David Eisenstat May 19 '15 at 12:04
  • 1
    The paper you cited shows that it is as hard as Boolean Matrix Multiplication, which may not be as hard as matrix multiplication. The firmest lower bound for testing triangle-freeness is O(n^2). I don't know that there is such an algorithm, but also have no proof that there is none. – Kittsil May 19 '15 at 19:47
  • Nice! That seems right to me. My wiki link is also nonsense and not proving anything. – Amtrix May 19 '15 at 20:38
0

Proved lower bound for triangle listing algorithm is O(n^3) or O(m^1.5), here n is the number of vertices and m is the number of edges. If you want to solve triangle counting with Matrix Multiplication method, the time complexity is same as Matrix Multiplication.

You should list more details of your question. Maybe the graph has some special property.

Bin Wu
  • 11
  • 2