A Polynomial Algorithm for the 2-Path Problem for Semicomplete Digraphs
Jørgen Bang‐Jensen, Caresten Thomassen · SIAM Journal on Discrete Mathematics · 1992
This paper presents polynomially bounded algorithms for finding a cycle through any two prescribed arcs in a semicomplete digraph and for finding a cycle through any two prescribed vertices in a complete k-partite oriented graph. It is also shown that the problem of finding a maximum transitive subtournament of a tournament and the problem of finding a cycle through a prescribed arc set in a tournament are both NP-complete.