Any way to find a 3-vertex cycle in a graph using an incidence matrix in O(nm) time?

Question

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:

1. Set up an array of vertices.

2. Go ---> in the matrix and build edges by assigning them in the matrix.

3. Each time edge is assigned check if that edge on both sides has a vertex with 2+ edges out.

4. 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].

5. 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:

https://en.wikipedia.org/wiki/Incidence_matrix

Answer 1

Let's assume first that your graph is connected, so that $m \geq n-1$. Convert your incidence matrix into an adjacency matrix in time $O(n^2) = O(nm)$. Now go over all $m$ edges, and for each edge $(i,j)$, go over all vertices $k$ and check in $O(1)$ whether $i,j,k$ is a triangle in the graph (using the adjacency matrix), for an overall running time of $O(nm)$.

If your graph is not connected, then use DFS/BFS to find its connected components, and run the procedure above on each of them. Assuming that the $i$th connected component consists of $n_i$ vertices and $m_i$ edges, the running time is $O(\sum_i n_i m_i) \leq O(\sum_{ij} n_i m_j) = O(nm)$.