I have a graph with n edges and m vertices. This is an undirected graph.
I need to find a 3 vertex cycle. Only 3.
I'm confident I need to use an incidence matrix for this as this seems to be the best data structure. I'm familiar with cycle finding algorithms and they are all in crazy polynomial or even exponential time.
However those are for general cycles. Not 3 vertex cycles. I have O(n*m) time.
Any ideas on how to find this 3-vertex cycle in an undirected graph using an incidence matrix?
First off you can discard any row with less than 2 "1"s. Then I think I need to see some kind of a pattern in the matrix for the 3 vertex cycle. Not seeing it at the moment.
EDIT Current idea:
Set up an array of vertices.
Go ---> in the matrix and build edges by assigning them in the matrix.
Each time edge is assigned check if that edge on both sides has a vertex with 2+ edges out.
If it has check if any of those edges out go to the same vertex [compare both lists for direct outward vertices from both sides of this edge].
If it's the same must be a 3 vertex loop.
I guess that's like rebuilding from incidence matrix to incidence list.
I'm looking at the below image from wikipedia: