Find the nodes that form a 3 length cycles?

1

I have been solving some questions based on graphs and cycles. I have decided to frame a question on cycles in Graphs.

Given an undirected graph having N number of vertices (numbered from 1 to N) and E edges. How to find the vertices that form 3 length cycles. Here the 3 length means 3 edges in the cycle path.
First line contains N and E
Following E lines contains undirected edges.

Example:
6 8
1 3
2 3
2 4
2 5
3 5
4 5
4 6
5 6

The above graph has 6 vertices and 8 edges.
The nodes that form 3 length cycles are:
2 3 4 5 6
because {2,3,5}, {2,4,5} and {4,5,6} form cycles.

I am able to do this in the Quadratic time.

My Approach:
dfs and check the common nodes between the vertices adjacency lists(can do this using a map of element and set of adjacency list elements). Add all of them to the set.
Finally print the set.

Could anyone suggest any approach to do this in O(n) or O(nlogn).
Any other approaches are always welcome :slight_smile:
Thank you :slight_smile:

@carre @everule1

2

“https://www.geeksforgeeks.org/cycles-of-length-n-in-an-undirected-and-connected-graph/”

it helps?

3

There’s a common squareroot decomposition solution for this problem.

Decompose your graph into 2 types of vertices. Let vertices of the first type be vertices which have >=sqrt(2*m) neighbours. All other vertices are vertices of the second type.

For all vertices of the first type(let’s call a vertex of the first type w), iterate over all edges (u-v) and check whether u-v-w forms a triangle.

This takes O(msqrt(m)) time.

This finds all cycles which have >=1 node/s of the first type.

To find vertices of the second type, iterate over all edges (u-v) such that the endpoints of this edge are both vertices of the second type. Then iterate over all neighbours of one of the endpoints and check if an edge exists between the endpoint and the other endpoint of the edge. If it exists, we have a triangle which only consists of nodes of the second type.

This is O(msqrtm) again

2 Likes
4

I have already that solution. Anyway thanks for the mention :slight_smile:

5

Thank you @im_nayeon