Hypergraphs are like simple graphs, except that instead of having edges that only connect 2 vertices, their edges are sets of any number of vertices. This happens to mean that all graphs are just a subset of hypergraphs.

It strikes me as odd, then, that I have never heard of any algorithms based on hypergraphs, or of any important applications, for modeling real-world phenomena, for instance. I guess that the superficial explanation is that it's a much more complex structure than a regular graph, and given this and its generality it's harder to make neat algorithms for, but I would expect there to be something!

Has anyone heard of a hypergraph-based algorithm, or application? It perplexes me that ordinary graphs can be so wonderfully useful, but their big brothers have nothing to offer.

3more comments