Hypertree
{{Short description|Generalization of tree graphs to hypergraphs}}
{{other uses}}
In the mathematical field of graph theory, a hypergraph {{mvar|H}} is called a hypertree if it admits a host graph {{mvar|T}} such that {{mvar|T}} is a tree. In other words, {{mvar|H}} is a hypertree if there exists a tree {{mvar|T}} such that every hyperedge of {{mvar|H}} is the set of vertices of a connected subtree of {{mvar|T}}.{{harvtxt|Brandstädt|Dragan|Chepoi|Voloshin|1998}} Hypertrees have also been called arboreal hypergraphs{{harvtxt|Berge|1989}} or tree hypergraphs.{{harvtxt|McKee|McMorris|1999}}
Every tree {{mvar|T}} is itself a hypertree: {{mvar|T}} itself can be used as the host graph, and every edge of {{mvar|T}} is a subtree of this host graph. Therefore, hypertrees may be seen as a generalization of the notion of a tree for hypergraphs.{{harvtxt|Berge|1989}}; {{harvtxt|Voloshin|2002}} 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 {{mvar|S}} of its hyperedges has the property that every two hyperedges in {{mvar|S}} have a nonempty intersection, then {{mvar|S}} itself has a nonempty intersection (a vertex that belongs to all hyperedges in {{mvar|S}}).{{harvtxt|Berge|1989}}; {{harvtxt|Voloshin|2002}}
By results of Duchet, Flament and SlaterSee, e.g., {{harvtxt|Brandstädt|Le|Spinrad|1999}}; {{harvtxt|McKee|McMorris|1999}} hypertrees may be equivalently characterized in the following ways.
- A hypergraph {{mvar|H}} is a hypertree if and only if it has the Helly property and its line graph is a chordal graph.
- A hypergraph {{mvar|H}} is a hypertree if and only if its dual hypergraph {{mvar|H{{sup|*}}}} is conformal and the 2-section graph of {{mvar|H{{sup|*}}}} is chordal.{{harvtxt|Berge|1989}}
- A hypergraph is a hypertree if and only if its dual hypergraph is alpha-acyclic in the sense of Fagin.{{harvtxt|Fagin|1983}}
It is possible to recognize hypertrees (as duals of alpha-acyclic hypergraphs) in linear time.{{sfnp|Tarjan|Yannakakis|1984}}
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.{{harvtxt|Brandstädt|Leitert|Rautenbach|2012}}
See also
- Dually chordal graph, a graph whose maximal cliques form a hypertree
Notes
{{reflist|30em}}
References
{{refbegin|30em}}
- {{citation
| last = Berge | first = Claude | authorlink = Claude Berge
| title = Hypergraphs: Combinatorics of Finite Sets
| publisher = North Holland | location = Amsterdam | isbn = 0-444-87489-5
| series = North-Holland Mathematical Library | volume = 45
| mr = 1013569
| year = 1989}}.
- {{citation
| last1 = Brandstädt | first1 = Andreas | author1-link = Andreas Brandstädt
| last2 = Dragan | first2 = Feodor
| last3 = Chepoi | first3 = Victor
| last4 = Voloshin | first4 = Vitaly
| title = Dually chordal graphs
| journal = SIAM Journal on Discrete Mathematics
| volume = 11
| pages = 437–455
| mr = 1628114
| url = http://pageperso.lif.univ-mrs.fr/~victor.chepoi/DualChGr.pdf
| year = 1998 | issue = 3 | doi=10.1137/s0895480193253415}}.
- {{citation
| last1 = Brandstädt
| first1 = Andreas
| author1-link = Andreas Brandstädt
| last2 = Le
| first2 = Van Bang
| last3 = Spinrad
| first3 = Jeremy
| title = Graph Classes: A Survey
| publisher = SIAM Monographs on Discrete Mathematics and Applications
| year = 1999
| mr = 1686154
| isbn = 0-89871-432-X
| url-access = registration
| url = https://archive.org/details/graphclassessurv0000bran
}}.
- {{citation
| last1 = Brandstädt | first1 = Andreas | author1-link = Andreas Brandstädt
| last2 = Leitert | first2 = Arne
| last3 = Rautenbach | first3 = Dieter
| contribution = Efficient dominating and edge dominating sets for graphs and hypergraphs
| series = Lecture Notes in Computer Science
| title = Algorithms and Computation: 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19-21, 2012, Proceedings
| volume = 7676
| pages = 267–277
| year = 2012
| doi = 10.1007/978-3-642-35261-4_30
| mr = 3065639
| arxiv = 1207.0953| isbn = 978-3-642-35260-7 }}.
- {{citation
| last = Fagin | first = Ronald | author-link = Ronald Fagin
| title = Degrees of acyclicity for hypergraphs and relational database schemes
| mr = 0709831
| doi = 10.1145/2402.322390
| journal = Journal of the ACM
| volume = 30
| pages = 514–550
| year = 1983| issue = 3 | doi-access = free
}}.
- {{citation
| last1 = McKee | first1 = T.A.
| last2 = McMorris | first2 = F.R.
| series = SIAM Monographs on Discrete Mathematics and Applications
| title = Topics in Intersection Graph Theory
| year = 1999
| isbn = 0-89871-430-3
| publisher = Society for Industrial and Applied Mathematics | location = Philadelphia, PA
| mr = 1672910}}.
- {{citation
| last1 = Tarjan | first1 = Robert E. | author1-link = Robert Tarjan
| last2 = Yannakakis | first2 = Mihalis | author2-link = Mihalis Yannakakis
| doi = 10.1137/0213035
| issue = 3
| journal = SIAM Journal on Computing
| mr = 749707
| pages = 566–579
| title = Simple linear-time algorithms to test chordality of graphs, test acyclicity of hypergraphs, and selectively reduce acyclic hypergraphs
| volume = 13
| year = 1984| url = http://dml.cz/bitstream/handle/10338.dmlcz/143237/Kybernetika_49-2013-1_2.pdf
}}.
- {{citation
| last = Voloshin | first = Vitaly
| series = Fields Institute Monographs
| volume = 17
| title = Coloring Mixed Hypergraphs: Theory, Algorithms and Applications
| publisher = American Mathematical Society | location = Providence, RI
| year = 2002
| isbn = 0-8218-2812-6
| mr = 1912135}}.
{{refend}}