On Convex Subsets in Tournaments
David J. Haglin, Marty J. Wolf · SIAM Journal on Discrete Mathematics · 1996
A tournament is a complete directed graph. A convex subset is a vertex subset with the property that every two-path beginning and ending inside the convex subset is contained completely within the subset. This paper shows that every nontrivial convex subset is the closure of a subset of vertices of cardinality two. This result leads to algorithms that find all convex subsets in a tournament in $O(n^4 )$ serial time and in $O(\log ^2 n)$ parallel time using $O(n^4)$ processors. Several variations of the problem that are solvable with this new algorithm are also presented.