Encyclopedia

GYO algorithm

Wikipedia contributorsAdapted for Fathomly · View authors

2 min read
Source updated March 20, 2026

The GYO algorithm 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.

01Definition

A hypergraph is a generalization of a graph. Formally, a hypergraph $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.

02Principle of the algorithm

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

Formally, we say that a hyperedge e of a hypergraph $H$ is an ear if one of the following two conditions holds:

$e$ is isolated, i.e., for every other hyperedge $e'$ , we have $e\cap e'=\emptyset$ ;
$e$ is almost covered by another hyperedge, i.e., there exists another hyperedge $f$ such that all vertices in $e\setminus f$ occur only in $e$ .

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:

The GYO algorithm ends on the empty hypergraph if and only if H is $\alpha$ -acyclic

Assume first the GYO algorithm ends on the empty hypergraph, let $e_{1},\ldots ,e_{m}$ be the sequence of ears that it has found, and let $H_{0},\ldots ,H_{m}$ the sequence of hypergraphs obtained (in particular $H_{0}=H$ and $H_{m}$ is the empty hypergraph). It is clear that $H_{m}$ , the empty hypergraph, is $\alpha$ -acyclic. One can then check that, if $H_{n}$ is $\alpha$ -acyclic then $H_{n-1}$ is also $\alpha$ -acyclic. This implies that $H_{0}$ is indeed $\alpha$ -acyclic.

For the other direction, assuming that $H$ is $\alpha$ -acyclic, one can show that $H$ has an ear $e$ . Since removing this ear yields an hypergraph that is still acyclic, we can continue this process until the hypergraph becomes empty.

Watch videos about GYO algorithmExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “GYO algorithm”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.

GYO algorithm

01Definition

02Principle of the algorithm

Sources and credits

Related topics

Yannakakis algorithm