  It is well-known and easy to show that even the following version of the
directed travelling salesman problem is NP-complete: Given a strongly connected
complete digraph $D=(V,A)$, a cost function $w: A\rightarrow \{0,1\}$ and a
natural number $K$; decide whether $D$ has a directed Hamiltonian cycle of cost
at most $K$. We study the following variant of this problem for
$\{0,1\}$-weighted semicomplete digraphs where the set of arcs which have cost
1 form a collection of vertex-disjoint complete digraphs. A digraph is
\textbf{semicomplete multipartite} if it can be obtained from a semicomplete
digraph $D$ by choosing a collection of vertex-disjoint subsets
$X_1,\ldots{},X_c$ of $V(D)$ and then deleting all arcs both of whose
end-vertices lie inside some $X_i$. Let $D$ be a semicomplete digraph with a
cost function $w$ as above, where $w(a)=1$ precisely when $a$ is an arc inside
one of the subsets $X_1,\ldots{},X_c$ and let $D^*$ be the corresponding \smd{}
that we obtain by deleting all arcs inside the $X_i$'s. Then every cycle $C$ of
$D$ corresponds to a {\bf generalized cycle} $C^g$ of $D^*$ which is either the
cycle $C$ itself if $w(C)=0$ or a collection of two or more paths that we
obtain by deleting all arcs of cost 1 on $C$. Similarly we can define a {\bf
generalized path} $P^g$ in a semicomplete multipartite digraph. The purpose of
this paper is to study structural and algorithmic properties of generalized
paths and cycles in semicomplete multipartite digraphs. This allows us to
identify classes of directed $\{0,1\}$-weighted TSP instances that can be
solved in polynomial time as well as others for which we can get very close to
the optimum in polynomial time. Along with these results we also show that two
natural questions about properties of cycles meeting all partite sets in
semicomplete multipartite digraphs are NP-complete.
