Hypertree

From HandWiki
Short description: Generalization of tree graphs to hypergraphs
A hypertree (blue vertices and yellow hyperedges) and its host tree (red)

In the mathematical field of graph theory, a hypergraph H is called a hypertree if it admits a host graph T such that T is a tree. In other words, H is a hypertree if there exists a tree T such that every hyperedge of H is the set of vertices of a connected subtree of T.[1] Hypertrees have also been called arboreal hypergraphs[2] or tree hypergraphs.[3]

Every tree T is itself a hypertree: T itself can be used as the host graph, and every edge of T is a subtree of this host graph. Therefore, hypertrees may be seen as a generalization of the notion of a tree for hypergraphs.[4] They include the connected Berge-acyclic hypergraphs, which have also been used as a (different) generalization of trees for hypergraphs.

Properties

Every hypertree has the Helly property (2-Helly property): if a subset S of its hyperedges has the property that every two hyperedges in S have a nonempty intersection, then S itself has a nonempty intersection (a vertex that belongs to all hyperedges in S).[5]

By results of Duchet, Flament and Slater[6] hypertrees may be equivalently characterized in the following ways.

  • A hypergraph H is a hypertree if and only if it has the Helly property and its line graph is a chordal graph.
  • A hypergraph H is a hypertree if and only if its dual hypergraph H* is conformal and the 2-section graph of H* is chordal.[7]
  • A hypergraph is a hypertree if and only if its dual hypergraph is alpha-acyclic in the sense of Fagin.[8]

It is possible to recognize hypertrees (as duals of alpha-acyclic hypergraphs) in linear time.[9] The exact cover problem (finding a set of non-overlapping hyperedges that covers all the vertices) is solvable in polynomial time for hypertrees but remains NP-complete for alpha-acyclic hypergraphs.[10]

See also

Notes

  1. (Brandstädt Dragan)
  2. (Berge 1989)
  3. (McKee McMorris)
  4. (Berge 1989); (Voloshin 2002)
  5. (Berge 1989); (Voloshin 2002)
  6. See, e.g., (Brandstädt Le); (McKee McMorris)
  7. (Berge 1989)
  8. (Fagin 1983)
  9. Tarjan & Yannakakis (1984).
  10. (Brandstädt Leitert)

References