# Algorithm for finding cycles in a hypergraph

Define a hypergraph as a set $V$ of vertices and a set $E$ of hyperedges, where a hyperedge is a non-empty subset of $V$. (This is a generalisation of an undirected graph, in which edges are allowed to connect any number of nodes, rather than just two.)

Define a cycle in a hypergraph as a cyclic sequence $C$ of vertices $v_0,v_1,\dots,v_n,v_0$, such that

(i) there is no hyperedge that includes all of the members of $C$; and

(ii) for every adjacent pair of vertices in $C$, there is a hyperedge that includes them both.

I'm looking for a simple and straightforward algorithm to detect whether any given hypergraph has a cycle. I feel like it should be obvious but it's not coming to me.

In case it helps: the hypergraphs I'm dealing with are reduced (meaning that no hyperedge is a subset of any other hyperedge), and also have the property that there is at least one hyperedge that contains each vertex.

Yes, there is a simple and efficient algorithm for this.

Given a hypergraph $H=(V,E)$, construct an undirected graph $G$ as follows: add the edge $(u,v)$ to $G$ if there is a hyperedge that contains both $u$ and $v$. Find the connected components of $G$.

Your condition (ii) is now equivalent to: $v_0,v_1,\dots,v_n$ are all in the same connected component. Thus, you want to find a subset of vertices that are all in the same connected component, but aren't contained in any hyperedge.

This leads to a simple algorithm. Iterate over the connected components of $G$. Let $S$ denote the set of vertices in one connected component of $G$. Test whether $S$ is contained in any hyperedge of $H$. If it isn't, then the hypergraph has a cycle (any cycle in $G$ that visits each vertex of $S$ at least once, and doesn't visit any vertex outside $S$, is a cycle in $H$). If after testing all the connected components of $G$, none of them are a valid cycle, then the hypergraph doesn't have any cycles.

(You don't need to test any of the subsets of $S$. If $S$ isn't a cycle, then none of the subsets will form a cycle, either. Why? If $S$ violates condition (i), then every subset of $S$ will violate condition (i), too.)

• I'm accepting this because it is a perfect answer to the problem as I posted it. However, in going through it I realised that the definition I gave was probably not the definition I really wanted to give, so I will leave some comments about that in order to be helpful for future visitors. – Nathaniel Nov 10 '17 at 6:47
• Suppose the vertices of a hypergraph are A, B and C, and that the hyperedges are {A, B, C} and {B, C, D}. My definition would count A, B, D, C, A as a cycle, which isn't the sort of thing I really wanted to include. – Nathaniel Nov 10 '17 at 6:52
• After reading around the topic I found that there is an existing definition of an "acyclic" hypergraph that suits my needs. This is the definition called $\alpha$-acyclicity described on Wikipedia. Weirdly, to define this one does not start from a definition of a cycle and then define an acyclic hypergraph as one that does not contain a cycle. (Though there have been attempts to do this - see Jégou et al 'on the notion of cycles in hypergraphs'.) – Nathaniel Nov 10 '17 at 6:57
• There is a straightforward algorithm to detect $\alpha$-acyclicity, called "GYO reduction", which also makes the definition easy to undestand. A good overview is given in these lecture notes. – Nathaniel Nov 10 '17 at 6:59
• (gah, typo in my second comment: the vertices are A, B, C, and D, obviously.) – Nathaniel Nov 10 '17 at 7:00