The bipartite travelling salesman problem: A pyramidally solvable case

Given k blue cities, k red cities and a 2k×2k distance matrix, the task in the bipartite travelling salesman problem is to find a shortest tour which alternately visits blue and red cities. We consider the special case of Van der Veen distance matrices and show that it remains NP-hard in general but can be solved in O(k2) time when all vertices with odd indices are blue and all with even indices are red.