3
$\begingroup$

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?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thank you! I am familiar with some of the research by these authors, but by no means all of it, they have MANY publications. There is a variant which I am interested in; it goes as follows: let there be an edge-2-coloring of the arcs. Let a path be alternating if the colors of the path alternate. I am interested in the variant of the problems when you require that the Hamiltonian path is alternating. The authors you cite have work on these kinds of paths, but I cannot find anything to this effect. Do you happen to know if this is known? Thank you once again! $\endgroup$
    – EGME
    Commented Nov 4, 2019 at 18:56
  • $\begingroup$ @EGME Very interesting; I was suspecting that finding a Hamiltonian alternating path in a 2-arc-colored semicomplete bipartite digraph would be doable in polynomial-time, but I couldn't find a reference easily. But I'd start with "Alternating cycles and paths in edge-coloured multigraphs: A survey" by Bang-Jensen and Gutin. If you can't find the result, you could just email them and ask about it. Feel free to ask another question here too. $\endgroup$
    – Juho
    Commented Nov 4, 2019 at 20:21
  • $\begingroup$ Thank you ... I will check the survey ... I probably will write to them. We just settled one of their conjectures after all. I will post another question though. I am looking for a “best possible” digraph problem involving Hamilton paths according to certain criteria. One of my criterions is that there be only one graph of a specific order and that the problem depend only on the arc directions and maybe something else ... but I need to think more about this. $\endgroup$
    – EGME
    Commented Nov 4, 2019 at 20:27
  • $\begingroup$ Thanks, I will. We just proved today that a slightly more complicated variant is NP-complete, but this one looks to be in P and very difficult to prove so ... I will update the other post ... have you seen it? T. $\endgroup$
    – EGME
    Commented Nov 6, 2019 at 20:24
  • $\begingroup$ Hi Juho, it seems we have proved it is in P ... a really beautiful proof it if pans out, my colleague is checking it (and often I make mistakes) .. hope I don’t have to backtrack on this ... t. EGME $\endgroup$
    – EGME
    Commented Nov 7, 2019 at 15:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.