1
$\begingroup$

The 3-Partition problem (wiki) is a $\text{NP}$-complete problem which is to decide whether a given multiset of integers can be partitioned into triples that all have the same sum. It is well-known that the 3SAT problem has a plenty of variants. Are there some variants of the 3-Partition problem discussed in the literature?

$\endgroup$
  • $\begingroup$ Did you try searching for any? You could immediately consider a variant where each integer occurs exactly or at most $k$ times, for some fixed $k$. $\endgroup$ – Juho Mar 8 '14 at 13:08
  • $\begingroup$ @Juho I searched and found little. Thanks for your hint. I would prefer to the variants which have been considered in the literature. $\endgroup$ – hengxin Mar 8 '14 at 13:13
2
$\begingroup$

One variant of 3-partition is the following distinct 3-partition problem, shown to be NP-complete in [1].

Distinct 3-partition

Input: A set $X = \{a_1,a_2,\ldots,a_{3n}\}$ of positive distinct integers, and a positive integer $B$ where $\Sigma_{i=1}^{3n} a_i = nB$, and $B/4 < a_i < B/2$, where $i \in [3n]$.

Question: Is there a partition of $X$ into $n$ triples such that the elements in each triple sum to $B$?

The problem is also NP-complete when $B$ is bounded above by a polynomial in $n$. For an "application", a reduction from the problem is used in [2] to show a certain graph problem is hard.


[1] H. Hulett, T.G. Will, G.J. Woeginger, Multigraph realizations of degree sequences: Maximization is easy, minimization is hard, Operations Research Letters 36 (2008) 594–596.

[2] Bonato, Anthony, Jeannette Janssen, and Elham Roshanbin. "Burning a graph is hard." arXiv preprint arXiv:1511.06774 (2015).

$\endgroup$

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.