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