Vertex heaviest paths and cycles in quasi-transitive digraphs.

Abstract

A digraph D is called a quasi-transitive digraph (QTD) 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 and z or from z to x. Solving a conjecture by Bang-Jensen and Huang (1995), Gutin (1995) described polynomial algorithms for finding a Hamiltonian cycle and a Hamiltonian path (if it exists) in a QTD. The approach taken in that paper cannot be used to find a longest path or cycle in polynomial time. We present a principally new approach that leads to polynomial algorithms for finding vertex heaviest paths and cycles in QTDs with non-negative weights on the vertices. This, in particular, provides an answer to a question by N. Alon on longest paths and cycles in QTDs.