Computing minimal extending sets by relation-algebraic modeling and development

• We develop a relation-algebraic specification of minimal extended sets.
• It can be directly executed by the ROBDD-based tool RelView.
• We discuss an alternative approach that sometimes is faster.
• We demonstrate applications of our algorithms.

In 2009 F. Brandt introduced minimal extending sets as a new tournament solution. Until now no efficient algorithm is known for their computation and, in fact, the NP-hardness of the corresponding decision problem has been proved quite recently by F. Brandt, P. Harrenstein and H.G. Seedig in a working paper. We develop a relation-algebraic specification of minimal extending sets. It is algorithmic and can be directly translated into the programming language of the ROBDD-based computer algebra system RelView. By this general and model-oriented approach we obtain almost the same efficiency as the specifically tailored program for minimal extending sets mentioned in another recent working paper of F. Brandt, A. Dau and H.G. Seedig. We also discuss an alternative approach that is based on testing the extending set property with relation-algebraic means, and a greedy strategy. Under favorable conditions it allows to solve much larger problem instances than our first solution and that of F. Brandt, A. Dau and H.G. Seedig.