Complexity of Hamilton path in directed complete bipartite graphs Finding a Hamiltonian path in a directed bipartite graph is NP-complete.  


  Problem 1 What is the complexity of the problem if we insist that the underlying graph of the digraph be complete bipartite? Is this known? (In other words, what is the complexity if the digraph is semicomplete bipartite, not just any bipartite digraph)


There is a variant of the problem we wish to consider


  Problem 2 What is the complexity of the problem if the underlying graph is complete bipartite (that is, the digraph is semicomplete bipartite), and we specify the starting and ending vertex of the path?
These problems can be solved efficiently.

For Problem 2, both [1] and [2] prove that the problem is solvable in $O(n^{2.5} / \log n)$ time. That is, this is the variant of Hamiltonian path with specific start and end vertices.

For Problem 1, i.e., when the input graph is a semicomplete bipartite digraph, it appears (see [3]) that a Hamiltonian path is found in polynomial-time via bipartite matching.

There's a good amount of research on these type of problems on tournaments and other digraphs. You will find more general results by looking at papers that cite the ones I mentioned.



[1]  J. Bang-Jensen, Y. Manoussakis, Weakly hamiltonian-connected vertices in bipartite tournaments, J. Combin. Theory B 63 (1995) 261–280.

[2] J. Bang-Jensen, G. Gutin, J. Huang, Weekly hamiltonian-connected ordinary multipartite tournaments, Discrete Math. 138 (1995) 63–74.

[3] J. Bang-Jensen, M. El Haddad, Y. Manoussakis, T. Przytycka, Parallel algorithms for the Hamiltonian cycle and Hamiltonian path problems in semicomplete bipartite digraphs, Algorithmica 17 (1997) 67–87.