The GYO algorithm^[1] is an algorithm that applies to hypergraphs. The algorithm takes as input a hypergraph and determines if the hypergraph is α-acyclic. If so, it computes a decomposition of the hypergraph.

The algorithm was proposed in 1979 by Graham and independently by Yu and Özsoyoğlu, hence its name.

Definition

A hypergraph is a generalization of a graph. Formally, a hypergraph ${\displaystyle H=(V,E)}$ consists of a set of vertices V, and of a set E of hyperedges, each of which is a subset of the vertices V. Given a hypergraph, we can define its primal graph as the undirected graph defined on the same set of vertices, in which we put an edge between any two vertices which occur together in some hyperedge.

A hypergraph H is α-acyclic if it satisfies two conditions: being chordal and being conformal. More precisely, we say that H is chordal if its primal graph is a chordal graph. We say that H is conformal if, for every clique of the primal graph, there is a hyperedge of H containing all the vertices of the clique.

The GYO algorithm takes as input a hypergraph and determines if it is α-acyclic in this sense.

Principle of the algorithm

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

Formally, an ear of the hypergraph H is a hyperedge e which is "almost covered" by another hyperedge f, in the sense that the vertices of e can be split into two groups:

• vertices that only occur in e (and in no other hyperedge of H)
• vertices that occur in f.

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.

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

Running time

The algorithm can be made to work in linear time.

References

• Abiteboul, Serge; Hull, Richard; Vianu, Victor (1994-12-02). Foundations of Databases: The Logical Level (PDF). Reading, Mass.: Pearson. ISBN 978-0-201-53771-0. See Algorithm 6.4.4.

Notes