# zbMATH — the first resource for mathematics

A polynomial algorithm for the 2-path problem for semicomplete digraphs. (English) Zbl 0759.05041
Authors’ summary: 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.
Reviewer: G.Chaty (Paris)

##### MSC:
 05C20 Directed graphs (digraphs), tournaments 05C38 Paths and cycles 05C40 Connectivity 68R10 Graph theory (including graph drawing) in computer science 68Q25 Analysis of algorithms and problem complexity
Full Text: