Finding scores in tournaments

Abstract

A tournament T_n is an orientation of the complete graph on nvertices. We continue the algorithmic study initiated by 10 of recognizing various directed trees in tournaments. Hell and Rosenfeld studied the complexity of finding various oriented paths in tournaments by probing edge directions. Here, we investigate the complexity of finding a vertex of prescribed outdegree (or indegree) in the same model. We show that the complexity of finding a vertex of outdegree k( ≤ (n − 1)/2) in T_n is Θ(nk). This bound is in sharp contrast to the Θ(n) bound for selection in the case of transitive tournaments. We also establish tight bounds for finding vertices of prescribed degree from the adjacency matrix of general directed/undirected graphs. These bounds generalize the classical bound of 11 for finding a sink (a vertex of outdegree 0 and indegree n − 1) in a directed graph.