I need a reduction from “Restricted-3-partition” to “k-graph-partition” that can be done in polynomial time, but I have absolutely no clue how to start this off. Can anyone help me out with an approach?

Restricted-3-partition definition:

You get a set of n=3k integers a1,...,an and a value A, so that A/4 < ai < A/2 and the sum of all ai equals kA. All ai have at maximum polynomial size in n. The task is to decide, if the integers could be partitioned in triples, so that the sum of every triple equals A.

K graph partitioning is explained here

  • $\begingroup$ You are sure that k-graph-partition are in polinomial time? By the way, if you do this already have solution to your problem. Reduction meaning that you can construct an instance of problem B starting from A. In your case, you should construct an instanc of k-graph-partition with restricted-3-partition. $\endgroup$ – theantomc Jan 10 at 15:26

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.