Skip to main content
Computer Science

Return to Question

Tweeted twitter.com/StackCompSci/status/1191505530570842112
added 163 characters in body
Source Link
EGME
EGME
  • 275
  • 1
  • 6

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?

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?

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, and we specify the starting and ending vertex of the path?

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?

added 37 characters in body
Source Link
EGME
EGME
  • 275
  • 1
  • 6

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?

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, and we specify the starting and ending vertex of the path?

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 graph be complete bipartite? Is this known?

There is a variant of the problem we wish to consider

Problem 2 What is the complexity of the problem if the graph is complete bipartite, and we specify the starting and ending vertex of the path?

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?

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, and we specify the starting and ending vertex of the path?

added 221 characters in body
Source Link
EGME
EGME
  • 275
  • 1
  • 6

Finding a Hamiltonian path in a directed bipartite graph is NP-complete. What

Problem 1 What is the complexity of the problem if we insist that the graph be complete bipartite? Is this known?

There is the complexitya variant of the problem if we insist that the graph be complete bipartite? Is this known?wish to consider

Problem 2 What is the complexity of the problem if the graph is complete bipartite, and we specify the starting and ending vertex of the path?

Finding a Hamiltonian path in a directed bipartite graph is NP-complete. What is the complexity of the problem if we insist that the graph be complete bipartite? Is this known?

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 graph be complete bipartite? Is this known?

There is a variant of the problem we wish to consider

Problem 2 What is the complexity of the problem if the graph is complete bipartite, and we specify the starting and ending vertex of the path?

Source Link
EGME
EGME
  • 275
  • 1
  • 6