Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

All Questions

1
vote
2answers
160 views

Solve Hamilton Circuit with Hamilton Path

I want to show the reduction $HC \leq HP$. Let $G=(V,E)$ be my undirected graph. My idea is: For each edge $e=(u,v) \in E$ check whether $(V,E\backslash\{e\})$ has a Hamiltonian Path. If this is true ...
1
vote
1answer
131 views

Reducing one variant of Hamiltonian path to another

Define $A = \{<G,s,t> :G$ is un directed graph that has a Hamilton path from $s$ to $t\}$ $B = \{<G> :G$ is un directed graph that has a Hamilton path$\}$ I would like to show that $...
0
votes
1answer
113 views

Solving Hidoku problem using reduction to Hamilton path

It seems like people have discussed this reduction here: Is Hidoku NP complete? But it looks like the solution that was given only tells you if the Hidoku problem has a solution or not (if an ...
1
vote
1answer
960 views

How to build the Reduction from Hamiltonian Cycle problem to Subgraph isomorphism? [duplicate]

I'm trying to prove that the Subgraph isomorphism problem is NPC using the Hamiltonian Cycle problem. Unfortunately I feel (or don't understand) that the solution is "empty" and doesn't explain the ...
1
vote
0answers
765 views

Poly-time reduction from directed Hamiltonian Path to undirected HP, both with with known start and end

this is homework, so PLEASE do not give me the solution(!), but help me get there on my own. I've got to proof that directed Hamilton Path with fixed stard and ending and undirected Hamilton Path ...
0
votes
0answers
56 views

A polynomial reduction from HAMPATH to LONG-PATH [duplicate]

$\text{HAMPATH} = \{(G=(V,E),s',t')| \text{ G has a Hamilton path from s' to t' } \}$ $\text{LONG-PATH} = \{(G,s,t,k) | \text{G has a simple path p from s to t, length(p) $\geq$ k} \}$ I'm trying ...
1
vote
1answer
217 views

Proving DPATH is NP-complete by a reduction from HAMPATH

I have a language DPATH that I'm trying to complete is NP-complete. ...
2
votes
2answers
2k views

CNF Generator for Factoring Problems

I've been reading these: Fast Reduction from RSA to SAT CNF Generator for Factoring Problems (Also have C code implementation) I don't understand how the reduction from FACT to $3\text{-SAT}$ works. ...