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?

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?

Hamilton Circuit

The Dirac’s theorem states that: “For a Graph G with N vertices, if the degree of each vertex is atleast N/2 then, the Graph has a Hamilton Circuit.” Can the same be said if a graph has a Hamilton Circuit then the degree of each vertex is atleast N/2 ?

Simple hamilton cycle reduction


  • Input: A undirected graph G and 2 nodes s, t

  • Question: Does G contain a hamilton path from s to t?


  • Input: A undirected graph G and a nodes s

  • Question: Does G contain a hamilton cycle starting at s?

I wish to show HAMCYCLE is NP-hard

I’ll show this by doing $ HAMPATH \leq_p HAMCYCLE$ since HAMPATH is known to be NP-COMPLETE

Reduction is as follows

$ (G, s, t) \to (G’, s’)$

where $ s’ = s$ and for $ G’$ I will add one edge from $ t$ to $ s’$

This is polynomial time because we are adding only an edge

if $ (G, s, t) \in HAMPATH$ , then we know there is a hamilton path from s to t, our graph G’ will be $ (s’, \dots, t)$ but since we added a edge from $ t$ to $ s’$ then

$ (s’, \dots, t, s’)$ , a cycle, thus $ (G’,s’) \in HAMCYCLE$

Now doing the converse, if $ (G’, s’) \in HAMCYCLE$ then there exist a hamilton cycle from $ (s’, …, s’)$ that visits every node and comes back to s’ meaning there is a node $ t$ right before $ s$ to make this a hamilton path, thus $ (G, s, t) \in HAMPATH$

Above is my entire attempt. I was wondering if I could call on $ t$ in my reduction since its not used as a input in HAMCYCLE ?

Why is the circuit input to SUCCINCT HAMILTON PATH exponentially more efficient than the graph input to HAMILTON PATH?

I’m studying the definitions of succinct versions of normal NP-complete problems in Papadimitriou’s Computational Complexity. Why are succinctly represented circuits more efficient than graph representations of HAMILTON PATH? I know that the inputs to these circuits are exponentially short, but the circuits are large. Let’s say the input length to the circuit is $ n$ , then the circuit has to branch $ n$ times, making a total of $ 2^n$ states. Why is the circuit exponentially small? I mean we are representing the same information, without guaranteed repetitions. Why is graph inferior?