What are the Applications of Hypergraphs - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T17:39:28Z http://mathoverflow.net/feeds/question/13750 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs What are the Applications of Hypergraphs DoubleJay 2010-02-01T23:47:10Z 2012-09-20T08:28:05Z <p><a href="http://en.wikipedia.org/wiki/Hypergraph" rel="nofollow">Hypergraphs</a> 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.</p> <p>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!</p> <p>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.</p> http://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs/13754#13754 Answer by Gjergji Zaimi for What are the Applications of Hypergraphs Gjergji Zaimi 2010-02-02T00:19:52Z 2010-02-02T00:26:06Z <p>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 the proof of <a href="http://arxiv.org/abs/0903.1633" rel="nofollow"> Density Hales-Jewett Theorem</a> by Tim Austin. Multidimensional Szmeredi theorem is also be another key-word you might want to look up. The <a href="http://www.ams.org/mathscinet-getitem?mr=531279" rel="nofollow">Furstenberg-Katznelson theorem</a> can be proven using hypergraph methods. The mathematics subject classification is 05C65.</p> <p>And more importantly, take a look at <a href="http://terrytao.wordpress.com/" rel="nofollow"> What's new</a> and search for "hypergraphs" to see a lot of other results that involve hypergraph methods in their proofs.</p> <p>One more thing, for real world applications, hypergraph methods appear in various places including <a href="http://www.springerlink.com/content/r2564675w66p42u2/" rel="nofollow">declustering problems</a> which are quite important to scale up the performance of parallel databases.</p> http://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs/13755#13755 Answer by Leonid Dworzanski for What are the Applications of Hypergraphs Leonid Dworzanski 2010-02-02T00:22:10Z 2010-02-02T00:27:38Z <ul> <li>Hypergraphs can be used to model some concurrent processes.</li> </ul> <p>"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.</p> http://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs/13759#13759 Answer by Peter Arndt for What are the Applications of Hypergraphs Peter Arndt 2010-02-02T00:33:52Z 2010-02-02T00:33:52Z <p>Hypergraphs can arise as Bruhat-Tits buildings of groups, see e.g. <a href="http://projecteuclid.org/DPubS?service=UI&amp;version=1.0&amp;verb=Display&amp;handle=euclid.dmj/1184341240" rel="nofollow">here</a>.</p> <p>Some real world applications: <a href="http://www.ploscompbiol.org/article/info:doi%2F10.1371%2Fjournal.pcbi.1000385" rel="nofollow">In this article</a> 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.</p> http://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs/13760#13760 Answer by Ryan O'Donnell for What are the Applications of Hypergraphs Ryan O'Donnell 2010-02-02T00:35:57Z 2010-02-02T00:35:57Z <p>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. </p> <p>For just one of many possible examples, take a look at the following paper of Feige, Kim, and Ofek:</p> <p><a href="http://research.microsoft.com/en-us/um/redmond/groups/theory/feige/homepagefiles/witness5.9.06.pdf" rel="nofollow">http://research.microsoft.com/en-us/um/redmond/groups/theory/feige/homepagefiles/witness5.9.06.pdf</a></p> http://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs/13816#13816 Answer by Charles Stewart for What are the Applications of Hypergraphs Charles Stewart 2010-02-02T11:23:19Z 2010-02-02T11:33:45Z <p>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.</p> <p>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.</p> <p>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, likewise, programming languages must constrain the way they represent state, and one can often cleanly map the programming-driven constraints into reasonable constraints on the hypergraphs.</p> <p>The idea crops up again and in again the literature on graph transformations. A good stepping off point is Drewes, Habel, &amp; Kreowski, 1997, <a href="http://www.informatik.uni-bremen.de/theorie/teach/gratra/2004-1/Skript/hr.pdf" rel="nofollow">Hyperedge Replacement Graph Grammars</a>, In Rozenberg, <em>Handbook of Graph Grammars and Computing by Graph Transformations</em>.</p> http://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs/13842#13842 Answer by Konrad Swanepoel for What are the Applications of Hypergraphs Konrad Swanepoel 2010-02-02T18:04:58Z 2010-02-02T18:04:58Z <p><a href="http://en.wikipedia.org/wiki/Matroid" rel="nofollow">Matroids</a> and more generally, <a href="http://en.wikipedia.org/wiki/Greedoid" rel="nofollow">greedoids</a>, are special classes of hypergraphs. For these classes <a href="http://en.wikipedia.org/wiki/Greedy%5Falgorithm" rel="nofollow">greedy algorithms</a> give optimal solutions for optimization problems, and have low polynomial time complexity. Special cases are</p> <ul> <li>Kruskal's algorithm for finding minimal spanning trees, and</li> <li>Dijkstra's algorithm for finding shortest paths, both in weighted graphs.</li> </ul> <p>There are many other matroid algorithms. See for example </p> <ul> <li>Bixby and Cunningham's chapter in <a href="http://books.google.co.uk/books?id=XicsNQIrC3sC&amp;printsec=frontcover#v=onepage&amp;q=&amp;f=false" rel="nofollow">the Handbook of Combinatorics, volume 1</a>, or </li> <li>Jungnickel's book <a href="http://books.google.co.uk/books?id=oFeII9gMKx0C&amp;printsec=frontcover#v=onepage&amp;q=&amp;f=false" rel="nofollow">Graphs, networks and algorithms</a>.</li> </ul> http://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs/17591#17591 Answer by Dave Pritchard for What are the Applications of Hypergraphs Dave Pritchard 2010-03-09T10:15:56Z 2010-03-09T10:15:56Z <p>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).</p> <p>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).</p> <p>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 &amp; 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 <a href="http://sma.epfl.ch/~pritchar/math/2009/pritchard.phdthesis.pdf#chapter.2" rel="nofollow">my thesis</a> which then delves into linear programming relaxations for this approach.</p> http://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs/92770#92770 Answer by stevegt for What are the Applications of Hypergraphs stevegt 2012-03-31T20:12:54Z 2012-03-31T20:12:54Z <p>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: <a href="http://stackoverflow.com/questions/9953981/can-a-hypergraph-represent-a-nondeterministic-turing-machine">http://stackoverflow.com/questions/9953981/can-a-hypergraph-represent-a-nondeterministic-turing-machine</a></p> http://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs/107649#107649 Answer by vzn for What are the Applications of Hypergraphs vzn 2012-09-20T04:08:19Z 2012-09-20T04:21:14Z <p>probably many thms and applications of math that dont explicitly refer to hypergraphs are actually related to them implicitly &amp; 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 <em>that</em> 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").</p> <p>here is one key appearance/application of hypergraphs not mentioned so far. the erdos-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. this lemma shows up in numerous important lower bounds proofs in monotone circuit theory in computer science, including new versions that strengthen or generalize the lemma.[2]</p> <p>because of their particular role in these "bottleneck"-type proofs its not outlandish to conjecture that variations might be crucial in some future-established comp sci complexity class separations.</p> <p>[1] <a href="http://cstheory.stackexchange.com/questions/12641/detailed-materials-on-sunflowers" rel="nofollow">erdos-rado sunflowers survey/refs, TCS.se</a></p> <p>[2] <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.156.5526" rel="nofollow">The Monotone Complexity of k-Clique on Random Graphs</a> by Rossman, containing new stronger lemmas on "quasi sunflowers"</p> <p>[3] <a href="http://gowers.files.wordpress.com/2009/05/razborov2.pdf" rel="nofollow">Razborovs method of approximations</a> by WT Gowers</p> http://mathoverflow.net/questions/13750/what-are-the-applications-of-hypergraphs/107661#107661 Answer by Mark Grant for What are the Applications of Hypergraphs Mark Grant 2012-09-20T08:28:05Z 2012-09-20T08:28:05Z <p><a href="http://www.cis.upenn.edu/~lhuang3/wpe2/papers/gallo92directed.pdf" rel="nofollow">Directed hypergraphs</a> are used to model chemical reaction networks. This is closely related to the biological application Peter Arndt mentions in his answer.</p> <p>The reaction network and the underlying hypergraph are related via the <a href="http://en.wikipedia.org/wiki/Stoichiometry#Stoichiometry_matrix" rel="nofollow">stoichiometry matrix</a>, which is a matrix consisting of one's, zeros and minus ones which generalizes the <a href="http://en.wikipedia.org/wiki/Adjacency_matrix" rel="nofollow">adjacency matrix</a> of a graph. </p> <p>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 <a href="http://www.sciencedirect.com/science/article/pii/S0893965907002844#" rel="nofollow">this paper</a> by Can Özturan) and so gives another example of the type gowers mentions in his comment.</p>