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?
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 ?
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 ?
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?
Can $ C_n$ has $ 2*n$ Euler circuits and $ 3*n$ Hamilton paths in the Cyclic graphs?