## 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?

Posted on Categories proxies

## 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

HAMPATH

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

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

HAMCYCLE

• 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?

Posted on Categories proxies

## Hamilton path and Euler circuits in Cycle graph

Can $$C_n$$ has $$2*n$$ Euler circuits and $$3*n$$ Hamilton paths in the Cyclic graphs?