1
$\begingroup$

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.

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
2
$\begingroup$

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.)

Improve this answer
$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – N. Virgo
    Nov 10, 2017 at 6:47
  • $\begingroup$ 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. $\endgroup$
    – N. Virgo
    Nov 10, 2017 at 6:52
  • $\begingroup$ 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'.) $\endgroup$
    – N. Virgo
    Nov 10, 2017 at 6:57
  • 1
    $\begingroup$ 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. $\endgroup$
    – N. Virgo
    Nov 10, 2017 at 6:59
  • $\begingroup$ (gah, typo in my second comment: the vertices are A, B, C, and D, obviously.) $\endgroup$
    – N. Virgo
    Nov 10, 2017 at 7:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.