Paths and Cycles in Extended and Decomposable Digraphs

We consider digraphs -- called extended locally semicomplete digraphs, or extended LSD's, for short -- that can be obtained from locally semicomplete digraphs by substituting independent sets for vertices. We characterize Hamiltonian extended LSD's as well as extended LSD's containing Hamiltonian paths. These results as well as some additional ones imply polynomial algorithms for finding a longest path and a longest cycle in an extended LSD. Our characterization of Hamiltonian extended LSD's provides a partial solution to a problem posed by R. Haggkvist in [14]. Combining results from this paper with some general results derived for so-called totally \Phi-decomposable digraphs in [3], we prove that the longest path problem is polynomially solvable for totally \Phi 0 -decomposable digraphs - a fairly wide family of digraphs which is a common generalization of acyclic digraphs, semicomplete multipartite digraphs, extended LSD's and quasi-transitive digraphs. Similar results are obtained ..