A note on Woeginger's paper "Banks winners in tournaments are difficult to recognize"
Olivier Hudry*,
ENST et CERMSEM
Résumé.
Etant donné un tournoi T, un vainqueur de Banks de T est un sommet placé en tête d'un sous-tournoi
transitif maximal (par rapport à l'inclusion) quelconque de T. Woeginger a montré que savoir si un sommet
donné de T est un vainqueur de Banks constitue un problème NP-complet. Cependant, la détermination d'un
vainqueur de Banks de T peut se faire en temps polynomial, et plus précisément en temps linéaire par rapport à
la taille de T.
Mots clés :
Tournoi, vainqueur de Banks, complexité.
Abstract.
Given a tournament T, a Banks winner of T is the first vertex of any maximal (with respect to
inclusion) transitive subtournament of T. While Woeginger shows that recognizing whether a given vertex
of T is a Banks winner is NP-complete, the computation of a Banks winner of T is polynomial, and
more precisely linear with respect to the size of T.
Keywords :
Tournament, Banks winner, complexity.
AMS Classification :
05C20, 05C90, 68W01, 91C99.
*Ecole Nationale Supérieure des Télécommunications, 46 rue Barrault, 75634 Paris cedex 13.