Algorithms for finding maximum transitive subtournaments

The problem of finding a maximum clique is a fundamental problem for undirected graphs, and it is natural to ask whether there are analogous computational problems for directed graphs. Such a problem is that of finding a maximum transitive subtournament in a directed graph. A tournament is an orientation of a complete graph; it is transitive if the occurrence of the arcs xy and yz implies the occurrence of xz. Searching for a maximum transitive subtournament in a directed graph D is equivalent to searching for a maximum induced acyclic subgraph in the complement of D, which in turn is computationally equivalent to searching for a minimum feedback vertex set in the complement of D. This paper discusses two backtrack algorithms and a Russian doll search algorithm for finding a maximum transitive subtournament, and reports experimental results of their performance.