A digraph is semicomplete if it has no pair of non-adjacent vertices. It is complete if every pair of distinct vertices induces a 2-cycle. A digraph is semicomplete multipartite if it can be obtained from a semicomplete digraph D by choosing a collection of vertex-disjoint subsets X1,…,Xc of V(D) and then deleting all arcs both of whose end-vertices lie inside some Xi. We can also think of a semicomplete digraph as being obtained from a semicomplete multipartite digraph on the same vertex set and partite sets V1,…,Vc by adding the arcs of a semicomplete digraph Di on Vi for each partite set Vi. It is well known that both the hamiltonian path and the hamiltonian cycle problem can be solved in polynomial time for semicomplete multipartite digraphs. In this paper we study the complexity of finding a hamiltonian path or cycle in a semicomplete digraph S which is obtained as above from a semicomplete multipartite digraph D and semicomplete digraphs Di=(Vi,Ai), i∈[c] such that the path or cycle uses as few arcs of A1∪…Ac as possible. We obtain a number of results for the case when each Di is a complete digraph. Already this case is highly nontrivial in the cycle case and the complexity is still open. We show how to find a Hamiltonian path which uses as few arcs from the Di’s as possible in polynomial time and obtain a number of results, both structural and algorithmic on hamiltonian cycles that use the minimum or close to the minimum number of arcs from the Di’s. Our results imply the polynomial solvability of some special cases of the NP-complete {0,1}-TSP problem. Finally we show that two natural questions about properties of quasi-hamiltonian cycles, that is, cycles meeting all partite sets in semicomplete multipartite digraphs are NP-complete.

Abstract. Let [Formula: see text] be a digraph of order [Formula: see text]. We define the degree of vertex [Formula: see text] in [Formula: see text] to be [Formula: see text], where [Formula: see text] and [Formula: see text] are the out-degree and in-degree of [Formula: see text] in [Formula: see text], respectively. Let [Formula: see text] be a positive integer and let [Formula: see text] be any given subset of [Formula: see text] with [Formula: see text]. In this paper we show that if [Formula: see text] for all [Formula: see text], then for any integer partition [Formula: see text] with [Formula: see text] for each [Formula: see text], there are [Formula: see text] disjoint cycles containing exactly [Formula: see text] vertices of [Formula: see text], respectively. The degree condition [Formula: see text] is sharp in some sense and this result confirms the conjecture posed by Wang [J. Graph Theory, 34 (2000), pp. 154–162] as a corollary. The result in this paper implies a theorem on cycle-factors containing matchings in bipartite graphs. Further, the special case [Formula: see text] is a directed version of the Aigner–Brandt theorem on disjoint cycles in graphs.