# #StackBounty: #np-hardness #partition-problem A partition problem with order constraints

### Bounty: 50

In the `OrderedPartition` problem, the input is two sequences of $$n$$ positive integers, $$(a_i){iin [n]}$$ and $$(b_i)$${iin [n]}\$.
The output is a partition of the indices $$[n]$$ into two disjoint subsets, $$I$$ and $$J$$, such that:

1. $$sum_{iin I} a_i = sum_{jin J} a_i$$
2. For all $$iin I$$ and for all $$jin J$$: $$b_ileq b_j$$.

In other words, we have to first order the indices on a line such that the $$b_i$$ are weakly increasing, and then cut the line such that the sum of the $$a_i$$ in both sides is the same.

If all $$b_i$$ are the same, then condition 2 is irrelevant and we have an instance of the NP-hard `Partition` problem.
On the other hand, if all $$b_i$$ are different, then condition 2 imposes a single ordering on the indices, so there are only $$n-1$$ options to check, and the problem becomes polynomial. What happens in between these cases?

To formalize the question, define by `OrderedPartition[n,d]`, for $$1leq dleq n$$,
the problem restricted to instances of size $$n$$, in which the largest subset of identical $$b_i$$-s is of size $$d$$. So the easy case, when all $$b_i$$-s are different, is `OrderedPartition[n,1]`, and the hard case, when all $$b_i$$-s are identical, is `OrderedPartition[n,n]`.

More generally, For any $$n$$ and $$d$$, in any `OrderedPartition[n,d]` instance, the number of possible partitions respecting condition 2 is $$O(n 2^d)$$. Hence, if $$din O(log{n})$$, then `OrderedPartition[n,d]` is still polynomial in $$n$$.

On the other hand, for any $$n$$ and $$d$$, we can reduce from a `Partition` problem with $$d$$ integers to `OrderedPartition[n,d]`. Let $$p_1,ldots,p_d$$ be an instance of `Partition`. Define the instance `OrderedPartition[n,d]` by:

• For each $$iin {1,ldots,d}$$, let $$a_i := 2ncdot p_i$$ and $$b_i := 1$$.
• For each $$iin {d+1,ldots,n}$$, let $$a_i := 1$$ and $$b_i := i$$
[if $$n-d$$ is odd, make $$a_n:=2$$ such that the sum will be even].

Hence, if $$dinOmega(n^{1/k})$$, for any integer $$kgeq 1$$, then `OrderedPartition[n,d]` is NP-hard.

QUESTION: What happens in the intermediate cases, in which $$d$$ is super-logarithmic but sub-polynomial in $$n$$?

Get this bounty!!!

This site uses Akismet to reduce spam. Learn how your comment data is processed.