Paths and cycles in extended and decomposable digraphs (Q1356688)

An extended locally semicomplete digraph, or extended LSD for short, is a digraph that can be obtained from locally semicomplete digraphs by substituting independent sets for vertices. The paper characterizes Hamiltonian extended LSDs as well as extended LSDs containing Hamiltonian paths, implying polynomial algorithms for finding a longest path and a longest cycle in an extended LSD. It is shown that the longest path problem is polynomially solvable for totally \(\Phi_0\)-decomposable digraphs. Similar results are obtained for the longest cycle problem and other problems on cycles in subfamilies of totally \(\Phi_0\)-decomposable digraphs.