Computing minimal extending sets by relation-algebraic modeling and development

摘要

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.