GYO algorithm: Difference between revisions

Revision as of 05:17, 7 January 2024

Latest revision as of 07:46, 13 October 2024

(10 intermediate revisions by 5 users not shown)

Line 1:

{{One source|date=December 2023}}

The '''GYO algorithm'''<ref name="yu79">{{Citecite webbook |title chapter-url=https://doi.org/10.1109/CMPSAC.1979.762509 | doi=10.1109/CMPSAC.1979.762509 | chapter=An algorithm for tree-query membership of a distributed query {{!}}| title=COMPSAC 79. Proceedings. Computer Software and the IEEE Computer Society's Third International Applications Conference, Publication1979 {{!}}| IEEEdate=1979 Xplore| last1=Yu |url first1=https://ieeexploreC.ieeeT.org/abstract/document/762509 |access-date last2=2023-12-12Ozsoyoglu |website first2=ieeexploreM.ieeeZ.org | pages=306–312 }}</ref> is an algorithm that applies to [[hypergraph]]s. The algorithm takes as input a hypergraph and determines if the hypergraph is [[Acyclic hypergraph|α-acyclic]]. If so, it computes a decomposition of the hypergraph.

The algorithm was proposed in 1979 by [[Martin H. Graham|Graham]] and independently by Yu and [[Meral Özsoyoglu|Özsoyoğlu]], hence its name.

Line 16:

The algorithm iteratively removes the so-called ''ears'' of the hypergraph, until the hypergraph is fully decomposed.

Formally, anwe ''ear''say of the hypergraph ''H'' isthat a hyperedge ''e'' whichof isa "almosthypergraph covered"<math>H</math> byis anotheran hyperedgeear ''f'',if inone the sense thatof the verticesfollowing oftwo ''e'' can be split into twoconditions groupsholds:

* vertices that only occur in ''e'' (and in no other hyperedge of ''H'')

* <math>e</math> is ''isolated'', i.e., for every other hyperedge <math>e'</math>, we have <math>e \cap e' = \emptyset</math>;

* vertices that occur in ''f''.

* <math>e</math> is almost ''covered'' by another hyperedge, i.e., there exists another hyperedge <math>f</math> such that all vertices in <math>e \setminus f</math> occur only in <math>e</math>.

Equivalently, the hyperedge ''e'' is an ear if it is the only hyperedge of ''H'' there is another hyperedge ''f'' such that the vertices of ''e\f'' only occur in ''e'' and in no other hyperedge of ''H''. Particular cases of ears include isolated hyperedges (i.e., those whose intersection with all other hyperedges is empty), or hyperedges that are a subset of another hyperedge.

In particular, every edge that is a subset of another edge is an ear.

The GYO algorithm then proceeds as follows:

* Find an ear ''e'' in ''H''.

* Remove ''e'' and remove all vertices of ''H'' that are only in ''e''.

If the algorithm successfully eliminates all vertices, then the hypergraph is α-acylic. Otherwise, if the algorithm gets to a non-empty hypergraph that has no ears, then the original hypergraph was not α-acyclic.:

{{Proof|proof=Assume first the GYO algorithm ends on the empty hypergraph, let <math>e_1,\ldots,e_m</math> be the sequence of ears that it has found, and let <math>H_0,\ldots,H_m</math> the sequence of hypergraphs obtained (in particular <math>H_0 = H</math> and <math>H_m</math> is the empty hypergraph). It is clear that <math>H_m</math>, the empty hypergraph, is <math>\alpha</math>-acyclic. One can then check that, if <math>H_n</math> is <math>\alpha</math>-acyclic then <math>H_{n-1}</math> is also <math>\alpha</math>-acyclic. This implies that <math>H_0</math> is indeed <math>\alpha</math>-acyclic.

== Running time ==

For the other direction, assuming that <math>H</math> is <math>\alpha</math>-acyclic, one can show that <math>H</math> has an ear <math>e</math>.<ref>{{cite arXiv|last=Brault-Baron |first=Johann |title=Hypergraph Acyclicity Revisited |date=2014-03-27 |class=math.CO |eprint=1403.7076 }} See Theorem 6 for the existence of an ear</ref> Since removing this ear yields an hypergraph that is still acyclic, we can continue this process until the hypergraph becomes empty.|title=The GYO algorithm ends on the empty hypergraph if and only if H is <math>\alpha</math>-acyclic}}

The algorithm can be made to work in linear time.

== References ==

* {{Cite book |lastlast1=Abiteboul |firstfirst1=Serge |title=Foundations of Databases: The Logical Level |last2=Hull |first2=Richard |last3=Vianu |first3=Victor |date=1994-12-02 |publisher=Pearson |isbn=978-0-201-53771-0 |___location=Reading, Mass. |language=English | url=http://webdam.inria.fr/Alice/pdfs/all.pdf}} See Algorithm 6.4.4.

== Notes ==