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$
2
  • $\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, 2014 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, 2014 at 13:13

1 Answer 1

3
$\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 and acknowledge you have read our privacy policy.

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