Hypertree


In mathematics, 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. Hypertrees have also been called arboreal hypergraphs or tree hypergraphs.
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. They include the connected Berge-acyclic hypergraphs, which have also been used as a generalization of trees for hypergraphs.

Properties

Every hypertree has the 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.
By results of Duchet, Flament and Slater hypertrees may be equivalently characterized in the following ways.
It is possible to recognize hypertrees in linear time.
The exact cover problem is solvable in polynomial time for hypertrees but remains NP-complete for alpha-acyclic hypergraphs.