GYO algorithm
subject: Category:Graph algorithms
type: Algorithm
subject: Category:Database algorithms
description: algorithm for hypergraph acyclicity
title: The GYO algorithm ends on the empty hypergraph if and only if H is -acyclic
proof: Assume first the GYO algorithm ends on the empty hypergraph, let be the sequence of ears that it has found, and let the sequence of hypergraphs obtained . It is clear that , the empty hypergraph, is -acyclic. One can then check that, if is -acyclic then is also -acyclic. This implies that is indeed -acyclic. For the other direction, assuming that is -acyclic, one can show that has an ear . Since removing this ear yields an hypergraph that is still acyclic, we can continue this process until the hypergraph becomes empty.