Generalized paths and cycles in semicomplete multipartite digraphs

Jørgen Bang-Jensen, Yun Wang, Anders Yeo

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)$,…