8
$\begingroup$

I saw this problem:

A non increasing sequence of positive integers $m_1,m_2,..., m_k$ is said to be n-realizable if the set $I_n=\{1,2,..., n\}$ can be partitioned into $k$ mutually disjoint subsets $S_1,S_2,...,S_k$ such that $\sum_{x\in S_i} x = m_i$ for each $1\leq i \leq k$.

in the paper "PARTITION OF A SET OF INTEGERS INTO SUBSETS WITH PRESCRIBED SUMS", by Fu-Long Chen, Hung-Lin Fu, Yiju Wang and Jianqin Zhou

http://journal.taiwanmathsoc.org.tw/index.php/TJM/article/view/1028

They have solved the problem under certain constraints. But I can't find anything about its complexity in general. Does anyone know a reference about the complexity of this problem? It reminds me of the bin-packing problem, or in some sense, it is similar to the subset sum problem. So, I guess it must be NP-complete in general?

More precisely, I like to prove the NP-completeness for the fixed value of $k$, for example, when $k = 3, 4, \ldots$? In this case, it is very similar to bin-packing or knapsack problem, but as we want the equality it is different. Maybe there are variations of these problems that match my question?

Improve this question
$\endgroup$
7
  • 2
    $\begingroup$ I would be very surprised if this problem was NP-complete. $\endgroup$
    – domotorp
    Feb 28, 2015 at 19:33
  • 1
    $\begingroup$ @user24175 Is it known to be polynomial time solvable if every $S_i$ has cardinality 2? $\endgroup$
    – Mohammad Al-Turkistany
    Mar 1, 2015 at 11:47
  • $\begingroup$ @mohammad If every $S_i$ has cardinality $2$, then we can reduce the problem to bipartite matching as follows. Consider $n$ vertices, labelled $1$ to $n$. There is an edge between vertex $i$ and vertex $j$ if there is a value $t$ such that $i + j = m_t$. $\endgroup$
    – S. Pek
    Mar 3, 2015 at 10:30
  • $\begingroup$ @S.Pek That is incorrect. We need to find a restricted perfect matching with certain some ($\sum m_i$ ) If we want any perfect matching then the problem is polynomial time solvable. So, the problem probably is $NP$-complete even if every $S_i$ has cardinality 2. $\endgroup$
    – Mohammad Al-Turkistany
    Mar 3, 2015 at 12:13
  • $\begingroup$ @mohammad It is not $\sum m_i$, but rather $\sum_{x \in S_i} x = m_i$. $\endgroup$
    – S. Pek
    Mar 3, 2015 at 12:46

2 Answers 2

Reset to default
3
$\begingroup$

For any fixed $k$, isn't it in P, by dynamic programming?

For each $i\in\{0,\ldots,n\}$ and $t_1, t_2, ..., t_k$ such that each $t_i \in \{0,\ldots,m_i\}$, define $S(i, t_1, t_2, \ldots, t_k)$ to be true iff $(t_1, t_2, .., t_k)$ is $i$-realizable. Then there are $O(n^{2k+1})$ such subproblems (assuming WLOG that $\max_i m_i\le n^2$), and you have a recurrence like

$ S(i, t_1, t_2, \ldots, t_k)$

$~ = S(i-1, t_1 - i, t_2, \ldots, t_k) $

$~\vee~ S(i-1, t_1, t_2 - i, t_3, \ldots, t_k)$

$~\vee~ \cdots$

$~\vee~ S(i-1, t_1, t_2 , t_3, \ldots, t_{k-1}, t_k- i)?$

Improve this answer
$\endgroup$
2
$\begingroup$

This problem is known to be NP-complete in the strong sense. See for instance
https://cstheory.stackexchange.com/questions/709/cutting-sticks-puzzle/713

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ @ Gamow: Thank you so much. But I actually had the proof that they suggested, by reduction from the partition problem instead of the 3-partition problem, quite a similar argument. I actually am looking for a proof that can be applied to any fixed value of $k$ (the number of sticks), for example, when $k=3$? Following the proof in that page, to achieve the NP-completeness for $k=3$, we have to set up, $a_1=1,\ldots,a_{3n}=N$, and $n=3$, which does not satisfy the conditions for the 3-partition problem, and indeed it is a very special instance of the problem! $\endgroup$
    – user24175
    Mar 9, 2015 at 7:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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