0
$\begingroup$

I'm trying to figure out how to reduce a 5 vertex graph to a Boolean equation that will answer if the graph contains a Hamiltonian path.

For a Hamiltonian Path to be present in a graph: Each vertex must be in the path exactly one time Each vertex must have an edge between them (except for the start and end vertex)

I'm not sure how to make this into a Boolean equation. I start by labeling all the vertexes $$V_{1}, V_{2}, V_{3}, V_{4}, V_{5}$$

An now through some combination of and, or, and not, I need to express the above properties. Any ideas?

$\endgroup$
0
$\begingroup$

This paper explains the technique for doing such a reduction: http://www.cse.msu.edu/~torng/Classes/Archives/cse830.03fall/Lectures/example-reductions.pdf

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ That URL is behind a login... $\endgroup$ – Julian A. Jan 6 '17 at 23:25
  • $\begingroup$ This URL is behind a login. Can you please share the document. Thanks $\endgroup$ – Gardezi May 8 '17 at 0:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.