Polynomial algorithms for finding paths and cycles in quasi-transitive digraphs.
Gregory Gutin · 1994
A digraph D is called quasi-transitive if for any triple x; y; z of distinct vertices of D such that (x; y) and (y; z) are arcs of D there is at least one arc from x to z or from z to x. A minimum path factor of a digraph D is a collection of the minimum number of pairwise vertex disjoint paths covering the vertices of D. J. Bang-Jensen and J. Huang conjectured that there exist polynomial algorithms for the Hamiltonian path and cycle problems for quasi-transitive digraphs. We solve this conjecture by describing polynomial algorithms for finding a minimum path factor and a Hamiltonian cycle (if it exists) in a quasi-transitive digraph. 1 Introduction A digraph D is called quasi-transitive if for any triple x; y; z of distinct vertices of D such that (x; y) and (y; z) are arcs of D there is at least one arc from x to z or from z to x. A digraph obtained by replacing each edge of a complete k-partite (k 2) graph by an arc or a pair of mutually opposite arcs with the same end vertices is...