1
$\begingroup$

Show that Integer parition problem is NP-complete using the fact that Hamiltonian cycle is NP-Complete

My Thoughts :
Integer paritition problem is about partitioning a given set of integers into two sets with equal
sums. If I could show that Integer partition is polynomially reducible to Hamiltonian cycle
that would prove the given statement. I am not really sure how an instance of solution to IP
could lead to a hamiltonian cycle

Improve this question
$\endgroup$
5
  • $\begingroup$ Showing that Integer Partition is polynomially reducible to Hamiltonian cycle would provide no information on whether Integer Partition is NP-hard. $\endgroup$ Commented Apr 6, 2021 at 8:16
  • $\begingroup$ But Given the fact that Hamiltonian cycle is NP-complete. If I reduce Integer parition to HC won't it prove that Integer partition is also NP-complete ? Or if not. What you suggest how to approach the given problem ? $\endgroup$ Commented Apr 6, 2021 at 9:01
  • $\begingroup$ No, it won't. You need to reduce HC to Integer Partition. $\endgroup$ Commented Apr 6, 2021 at 9:30
  • $\begingroup$ okay got it. Any ideas how to approach that ? $\endgroup$ Commented Apr 6, 2021 at 9:40
  • $\begingroup$ Show that (the decision version of) Hamiltonian Path (HP) is in NP. Invoke the Cook-Levin theorem to establish the existence of a polynomial-time reduction $f$ from HP to the Boolean Satisfiability (SAT) problem. Use any well-known polynomial-time reduction $g$ from SAT to 3SAT (i.e., the restriction of SAT to boolean formulas that are conjunctions of clauses each consisting of a disjunction of 3 literals). Finally, reduce 3SAT to Integer Parition (IP) via any chain of reductions found in textbooks. Let $h$ be the combined reduction. Then $h \circ g \circ f$ is a reduction from HP to IP. $\endgroup$ Commented Apr 6, 2021 at 10:11

0

Reset to default

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.