8

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?

user24175
  • 375
  • 1
  • 8
  • 2
    I would be very surprised if this problem was NP-complete. – domotorp Feb 28 '15 at 19:33
  • 1
    @user24175 Is it known to be polynomial time solvable if every $S_i$ has cardinality 2? – Mohammad Al-Turkistany Mar 01 '15 at 11:47
  • @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$. – S. Pek Mar 03 '15 at 10:30
  • @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. – Mohammad Al-Turkistany Mar 03 '15 at 12:13
  • @mohammad It is not $\sum m_i$, but rather $\sum_{x \in S_i} x = m_i$. – S. Pek Mar 03 '15 at 12:46
  • @S.Pek Any perfect matching does not guarantee that each $m_i$ appears the right number of times in the matching. For instance, a perfect matching with all edges having $m_1$ is not a valid solution for the problem. – Mohammad Al-Turkistany Mar 03 '15 at 16:29
  • @user24175 The variant asking for a partition of $I_n$ with prescribed differences is NP-complete even if the cardinality of each $S_i$ is 2. I am working on a reduction from this problem to yours. – Mohammad Al-Turkistany Mar 09 '15 at 19:30

2 Answers2

3

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

Neal Young
  • 10,546
  • 33
  • 60
2

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

Community
  • 1
Gamow
  • 5,772
  • 6
  • 25
  • 39
  • 1
    @ 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! – user24175 Mar 09 '15 at 07:47