
Algorithms Algorithms and Data Structures  Analysis, Graph, Search, String, Sorting, Merge, Compression, Optimization, Quantum 
 LinkBack  Thread Tools  Display Modes 
June 16th, 2010, 09:44 PM  #1 
Joined: Jun 2010 Posts: 1  decide if a graph contains a triangle
Devise an algorithm that will decide if a given graph of n vertices and m edges does or does not contain a triangle (K3), in time O(max{n^2, mn}). I found this problem in ch.1 of Algorithms and Complexity by H S Wilf. Any ideas are appreciated. Or if you know of some place where an algorithm to do this is explained, tell me. Thanks. 
My Computer Forum is free to register and we welcome everyone! 
January 30th, 2011, 01:21 PM  #2 
Joined: Jan 2011 Posts: 1  Re: decide if a graph contains a triangle
My thoughts are, do a depth first transversal from any node to the rest. When you encounter an unvisited node, give it a number representing the distance from the first node, mark it as visited, and continue the transversal. When you encounter a node that is already visited, check if it is the one you visited 1 step back, which would result in a triangle. If it is not, continue the transversal to some other node. Code: bool ContainsTriangle(Node[] nodes) { for (int index = 0; index < nodes.length; index++) { //In case the graph is not connected. Node n = nodes[index]; if (n.visited) continue; n.visited = true; n.nr = 0; if (Visit(n)) return true; } return false; } bool Visit(Node n) { foreach (Node n2 in n.neighbors) { if (n2.visited) { if (n2.nr == n.nr  1) return true; continue; } n2.visited = true; n2.nr = n.nr + 1; if (Visit(n2)) return true; } return false; } Also, the foreach loop in total really only runs once pr edge, since it only runs over the edges going out of the current node. Now, it's been a long time since my algorithm course, so I probably messed up somewhere, but I get that to O(n + m), which seems strange considering the bound you got from your book.. 
December 28th, 2011, 11:50 AM  #3 
Joined: Dec 2011 Posts: 3  Re: decide if a graph contains a triangle
I would like to add something in this conversation: There is a theorem that states an upper bound to the number of edges that a graph could have without having a triangle: "Every graph with n vertices and more than (n^2)/4 edges has a triangle" So, if you build an algorithm to solve your problem, you could before test the condition from the theorem above. If there is more than (n^2/4) edges in the graph, you don't have to keep running the algorithm, because this graph will have a triangle. [FYI: I read about this theorem in Bollobas' book "Modern Graph Theory"] 

Tags 
decide, graph, triangle 
Thread Tools  
Display Modes  

Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Finding an acyclic orientation in a graph  Anonymous Coward  Algorithms  7  January 24th, 2010 12:28 PM 