47
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • 28
    $\begingroup$ A general comment here is that a hypergraph is an absurdly general object; it's basically an element of the power set of the power set of a set. For example, topologies and measurable spaces are both (technically) special cases of hypergraphs. So any theorems or applications necessarily need to focus on special cases. $\endgroup$
    – Qiaochu Yuan
    Commented Feb 2, 2010 at 4:21
  • 16
    $\begingroup$ Calling it a subset of the powerset makes it seem less intimidating =p. $\endgroup$
    – Harry Gindi
    Commented Feb 2, 2010 at 12:00
  • 8
    $\begingroup$ Here are two partial explanations for why algorithms based on hypergraphs are less common than algorithms based on graphs. 1. Some polynomial-time algorithms for graphs turn into NP-complete problems when you try to generalize them to hypergraphs (e.g., finding a perfect matching). 2. We often use graphs to model symmetric binary relations, and symmetric binary relations appear much more frequently than symmetric ternary relations (and beyond). $\endgroup$
    – gowers
    Commented Mar 31, 2012 at 21:20
  • 3
    $\begingroup$ @Harry Gindi: for me, it's just the other way roudn. Hypergraph? Cool. Subset of the powerset? Arrgh, complex stuff way over my head. :) $\endgroup$
    – Felix Goldberg
    Commented Sep 20, 2012 at 8:56
  • 7
    $\begingroup$ Hypergraphs also crop up in physics of many-body systems. Usual graphs are only good for modelling of the pairwise interaction. But oftentimes (for example in statistical physics and effective theories) one works with general interactions that depend on more than two particles. In this situation there is usually some restriction on the number of vertices a hyperedge can contain and this important class of hypergraphs is no longer absurdly general. $\endgroup$
    – Marek
    Commented Sep 20, 2012 at 9:03

15 Answers 15

Reset to default
24
$\begingroup$

I've done some work which made me appreciate the view that labelled hypergraphs are one of the most widely appropriate, general ways to represent data on stateful machines. In computer science, we commonly want to divide up state into a number of possibly overlapping data structures, which will contain and be referenced by pointers.

This lends itself to the following representation: data structures are hyperedges. Non-pointer data within data structures are labels of the associated hyperedge. And pointers are represented by vertices, possibly (not always!) needing an attribute to indicate which hyperedge is the source and which is the target of the pointer. Computation, then, is graph rewriting.

As Qiaochu says, hyperedges are absurdly general. Likewise, the notion of data. To make this useful, one needs to constrain the form the hyperedges take. What is nice is that the need to constrain the way that state is represented is perfectly matched with the need in useful programming languages to contrain the representation of data, and furthermore, one can often cleanly map the programming-driven constraints into reasonable constraints on the hypergraphs.

The idea crops up again and again the literature on graph transformations. A good stepping off point is Drewes, Habel, & Kreowski, 1997, Hyperedge Replacement Graph Grammars, In Rozenberg, Handbook of Graph Grammars and Computing by Graph Transformations.

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ This is a really good answer, but I was struggling to visualise what you're saying. Would you mind adding some simple diagrams of modelling the data as data and graph rewriting? $\endgroup$
    – CMCDragonkai
    Commented Jun 26, 2014 at 10:26
  • 2
    $\begingroup$ @CMCDragonkai - I really should put together some of these diagrams. A short, well-illustrated white paper on the topic would indeed make this point of view easier to explain. I have put this on my list of "hope to dos" $\endgroup$
    – Charles Stewart
    Commented Sep 11, 2014 at 10:50
  • 2
    $\begingroup$ @CharlesStewart This is really fascinating. I know you wrote the comment forever ago, but I'm wondering if you ever ended up returning to the idea to write that white paper? $\endgroup$
    – rp.beltran
    Commented Aug 6, 2020 at 21:32
19
$\begingroup$

Hypergraphs and various properties that we can prove about them are the basis of many techniques that are used in modern mathematics. I will mention Deducing the Density Hales–Jewett Theorem from an infinitary removal lemma by Tim Austin. Multidimensional Szmerédi theorem is also another key-word you might want to look up. The Furstenberg–Katznelson theorem (see An ergodic Szemerédi theorem for commuting transformations can be proven using hypergraph methods. The mathematics subject classification is 05C65.

And more importantly, take a look at Terry Tao's blog What's new and search for "hypergraphs" to see a lot of other results that involve hypergraph methods in their proofs.

One more thing, for real world applications, hypergraph methods appear in various places including declustering problems (see Liu and Wu - A Hypergraph Based Approach to Declustering Problems) which are quite important to scale up the performance of parallel databases.

Improve this answer
$\endgroup$
3
  • 4
    $\begingroup$ Here's another example for "real world" applications: research.microsoft.com/en-us/um/people/denzho/papers/hyper.pdf $\endgroup$
    – Felix Goldberg
    Commented Sep 20, 2012 at 8:58
  • $\begingroup$ I rolled back the previous edit which was incredibly minor and just tinkering with the OP's English to no significant effect, on a question which has long been inactive $\endgroup$
    – Yemon Choi
    Commented Dec 21, 2014 at 17:27
  • $\begingroup$ "Each edge contains all articles by its corresponding author" from the linked pdf. Wondering why not just have one edge per article instead. $\endgroup$
    – Lance Pollard
    Commented Feb 25, 2018 at 18:27
12
$\begingroup$

One example: A 3-uniform hypergraph is the natural way to model the variable/clause structure of a 3-Sat instance. Since 3-Sat is one of the most important algorithmic problems in computational complexity theory, hypergraphs play an important role there.

For just one of many possible examples, take a look at the paper of Feige, Kim, and Ofek: Witnesses for non-satisfiability of dense random 3CNF formulas.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Hypergraphs (with no uniformity restriction) are also the natural way to model clause sets of general SAT. Each hyperedge represents the single set of literals that is forbidden by some clause. These structures have also been studied in constraint satisfaction, under the name microstructure complements. The hyperedges are there colourfully called "nogoods", a name coined by Stallman and Sussman in 1976 (yes, the Richard Stallman). hdl.handle.net/1721.1/6255 $\endgroup$
    – András Salamon
    Commented Jul 20, 2010 at 17:34
11
$\begingroup$

Matroids and more generally, greedoids, are special classes of hypergraphs. For these classes greedy algorithms give optimal solutions for optimization problems, and have low polynomial time complexity. Special cases are

  • Kruskal's algorithm for finding minimal spanning trees, and
  • Dijkstra's algorithm for finding shortest paths, both in weighted graphs.

There are many other matroid algorithms. See for example

Improve this answer
$\endgroup$
11
$\begingroup$

Directed hypergraphs are used to model chemical reaction networks. This is closely related to the biological application Peter Arndt mentions in his answer.

The reaction network and the underlying hypergraph are related via the stoichiometry matrix, which is a matrix consisting of ones, zeros and minus ones which generalizes the adjacency matrix of a graph.

One obvious question you might ask about such a network is "are there any feedback loops"? This translates into the mathematical problem of finding directed hypercircuits in a directed hypergraph. This turns out to be an NP-complete problem (as shown in the 2008 paper On finding hypercycles in chemical reaction networks by Can Özturan) and so gives another example of the type Gowers mentions in his comment.

Improve this answer
$\endgroup$
10
$\begingroup$

Hypergraphs can arise as Bruhat-Tits buildings of groups, see e.g.

  • Alireza Sarveniazi. "Explicit construction of a Ramanujan (n1,n2,…,nd−1)-regular hypergraph." Duke Math. J. 139 (1) 141 - 171, 15 July 2007. doi:10.1215/S0012-7094-07-13913-9.

Some real world applications:

In the article

the authors list some applications to biology. Their nice starting example is that if one wants to model a chemical reaction one can write A-->B for a process which transforms A into B and see this as the edge of a graph. Sometimes such a process only works in the presence of some catalyzer (A+C-->B+C), making it a relation between three instead of two ingredients and giving a 2-edge of a hypergraph.

Improve this answer
$\endgroup$
9
$\begingroup$

Hypergraphs have been very useful algorithmically for the following "Steiner tree problem:" given a graph (V, E) with a specified "required/terminal" vertex subset R of V and a cost for each edge, find a minimum-cost set of edges which connects all the terminals (and includes whatever subset of V \ R you like). Any minimal solution is a tree all of whose leaves are terminals (a so-called Steiner tree).

Hypergraphs are useful because there is a "full component decomposition" of any Steiner tree into subtrees; the problem of reconstructing a min-cost Steiner tree from the set of all possible full components is the same as the min-cost spanning connected hypergraph problem (a.k.a. min hyper-spanning tree problem) for a hypergraph whose vertex set is R. That's the approach used by many modern algorithms for the Steiner tree problem (whether they are integer-program based exact algorithms that are actually implemented, or non-implemented approximation algorithms with good provable approximation guarantees).

I like this application since one must view the hypergraph as "like a graph" (want it to be connected and acyclic) and not like a set system. This approach was used implicitly starting around 1990 by Zelikovsky and brought out more explicitly around 1997 by (I think) Warme and Prömel & Steger. A very cute paper using this approach is coming out at STOC 2010 by Byrka et al. As an $\epsilon$-shameless self-reference, there is more information in my thesis which then delves into linear programming relaxations for this approach.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks! Updated the link. $\endgroup$
    – Dave Pritchard
    Commented May 22, 2022 at 22:30
6
$\begingroup$
  • Hypergraphs can be used to model some concurrent processes.

"it's a much more complex structure than a regular graph" Hypergraphs could be represented as ordinary graphs, if one represents each "hyperedge" with an additional ordinary node and ordinary edges which connect the new node with the nodes incident to "hyperedge". It makes me feel that hypergraphs aren't a strict subset.

Improve this answer
$\endgroup$
6
$\begingroup$

Probably many theorems and applications of math that don't explicitly refer to hypergraphs are actually related to them implicitly & could be recast in those terms. Because hypergraphs are equivalently just "sets of sets". In this way they're also often interchangeable with/analogous to a 2d boolean array in computer science (and how ubiquitous is that structure in both software and mathematics? In computer science it might be referred to as a "design pattern" or even just a simple "discrete structure").

Here is one key appearance/application of hypergraphs not mentioned so far. The Erdős–Rado sunflower lemmas[1], a key discovery of extremal graph/set theory, are about an intrinsic order or emergent "structure" to "random" hypergraphs if certain somewhat modest constraints are satisfied. These lemmas show up in numerous important lower bounds proofs in monotone circuit theory in computer science, including new versions that strengthen or generalize the lemma.[2]

Because of their particular role in these "bottleneck"-type proofs it's not outlandish to conjecture that variations might be crucial in some future-established computer science complexity class separations.

[1] Erdős–Rado sunflowers survey/refs, TCS.se

[2] The Monotone Complexity of $k$-Clique on Random Graphs by Rossman, containing new stronger lemmas on "quasi sunflowers"

[3] Razborov's method of approximations by WT Gowers

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ footnote— technically a hypergraph is equiv to the comp sci discrete stucture of a 2d set of arrays of booleans, or an unordered list of lists. but note in comp sci often lists that can be implemented as unordered are implemented as ordered ones because the array ordering is actually more efficient to implement than a set. $\endgroup$
    – vzn
    Commented Sep 20, 2012 at 4:31
5
$\begingroup$

Ford, Green, Konyagin, Maynard, and Tao - Long gaps between primes mentions a hypergraph covering theorem of Pippenger and Spencer. This theorem is generalized and used in a sieving method to find large intervals having only composite numbers.

Improve this answer
$\endgroup$
4
$\begingroup$

Every finite geometry (projective planes, generalized polygons, polar spaces, near polygons, etc.) and every block design (Witt design, difference sets, Steiner triple systems, etc.) is a hypergraph. So, all the applications of those objects can be considered as applications of hypergraphs.

For example, this paper discusses the application of finite projective planes in coding theory and cryptography: Storme - Applications of finite geometry in coding theory and cryptography. Inside mathematics, there are many other applications of these hypergraphs in group theory, extremal combinatorics and graph theory.

Improve this answer
$\endgroup$
3
$\begingroup$

Here is a "philosophy" I learned from a class on the combinatorics of hypergraphs taught by András Gyárfás (as part of the 'Budapest Semesters in Mathematics' program): sometimes statements that are just about graphs are actually easiest to prove by considering hypergraphs as well.

The canonical example given by Gyárfás is the following theorem of Erdős:

Theorem: For any $n,s$, there exists a graph with girth (length of shortest cycle) greater than $s$ and chromatic number greater than $n$.

Actually this theorem was proved by Erdős using the probabilistic method and he certainly had no need of hypergraphs to prove it.

However, the first explicit constructions of graphs as in the theorem above were given by Lovász in 1968 (citation below). Lovász's construction was inductive in nature, and the induction required him to consider, in apparently an essential way, not just graphs but also hypergraphs. Indeed, on the first page of this paper we find the quote: "It is to be mentioned, that I can not describe this construction for graphs using only graphs and no set systems."

Lovász, László, On chromatic number of finite set-systems, Acta Math. Acad. Sci. Hung. 19, 59-67 (1968). ZBL0157.55203.

Improve this answer
$\endgroup$
0
2
$\begingroup$

I believe a hypergraph can implement, or at least represent the transition states of, a nondeterministic Turing machine. Can't yet find any literature demonstrating that though, which makes me wonder. I have an open question about this over on StackOverflow right now, with no takers as of this writing: https://stackoverflow.com/questions/9953981/can-a-hypergraph-represent-a-nondeterministic-turing-machine

Improve this answer
$\endgroup$
1
$\begingroup$

The current (September, 2017) issue of IEEE Transactions on Pattern Analysis and Machine Intelligence (PAMI) contains:

on the use of hypergraphs for pattern clustering (and pattern classification).

Improve this answer
$\endgroup$
0
$\begingroup$

I'll go ahead and plug a paper of mine in the hopes it will generate more interest in it, Boolean formulae, hypergraphs, and combinatorial topology which I wrote with my student Oliver Thistlethwaite many years ago. If you look at the set of boolean formulae in $n$ variables in $k$-conjunctive normal form, denoted $k\operatorname{SAT}n$, this can be turned into a simplicial complex by using implication as an ordering relation. We proved that this simplicial complex is homotopy equivalent to the Alexander dual of the independence complex of $\operatorname{Cube}(n,n-k)$, the hypergraph of $n-k$-faces of an $n$ dimensional cube:

$$|k\operatorname{SAT}n|\simeq \Theta(\operatorname{Cube}(n,n-k))$$

where $\Theta$ is defined to be the simplicial complex where simplices are spanned by vertices of the hypergraph which are in the complement of at least one hyperedge. (This is equivalent to the Alexander dual of the independence complex, if you know what those are.)

These simplicial complexes seem rather complicated. We discovered that they are not just wedges of same dimensional spheres but in general have homology in multiple dimensions. (Though in the codimension $2$ case, they do seem to be wedges of spheres, see below.) I would love to understand these spaces better. For example, the following is still an open question:

Conjecture: $|\Theta(\operatorname{Cube}(n,n-2)|\simeq \vee_{(2n-3)!!}S^{2n-2}$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .