Generalized paths and cycles in semicomplete multipartite digraphs

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 X₁,…,X_c of V(D) and then deleting all arcs both of whose end-vertices lie inside some X_i. We can also think of a semicomplete digraph as being obtained from a semicomplete multipartite digraph on the same vertex set and partite sets V₁,…,V_c by adding the arcs of a semicomplete digraph D_i on V_i for each partite set V_i. 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 D_i=(V_i,A_i), i∈[c] such that the path or cycle uses as few arcs of A₁∪…A_c as possible. We obtain a number of results for the case when each D_i 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 D_i’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 D_i’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.