The Complexity of Color-constrained Paths in Semicomplete Multipartite Digraphs

Julian Brinkmann

Every semicomplete multipartite digraph contains a quasi-Hamiltonian path, but the problem of finding a quasi-Hamiltonian path with prescribed start and end vertex is NP-complete e…