GYO algorithm: Difference between revisions

Revision as of 05:17, 7 January 2024

Revision as of 15:31, 18 January 2024

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-emtpy hypergraph that has no ears, then the original hypergraph was not α-acyclic.

== Running time ==