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.

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.