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?