Quasi-hamiltonian paths in semicomplete multipartite digraphs

A quasi-hamiltonian path in a semicomplete multipartite digraph DD is a path which visits each maximal independent set (also called a partite set) of DD at least once. This is a generalization of a hamiltonian path in a tournament.In this paper we investigate the complexity of finding a quasi-hamiltonian path, in a given semicomplete multipartite digraph, from a prescribed vertex xx to a prescribed vertex yy as well as the complexity of finding a quasi-hamiltonian path whose end vertices belong to a given set of two vertices {x,y}{x,y}. While both of these problems are polynomially solvable for semicomplete digraphs (here all maximal independent sets have size one), we prove that the first problem is NP-complete and describe a polynomial algorithm for the latter problem.