# Is this partition problem strongly NP-complete?

Some computational problems have variants that appear to be harder. For instance, Graph Automorphism (GA) problem has quasi-polynomial time algorithm ( by Babai's Graph Isomorphism result) while the fixed-point free GA problem is NP-complete.

Partition problem is weakly NP-complete problem since it has pseudo-polynomial time algorithm. I am interested in variants that are strongly NP-complete.

Here is a variant of partition problem:

Restricted partition problem

Input: Set $S$ of $2N$ integers, and a collection of pairs $P$ from $S$

Query: Is there a partition of $S$ into two equal cardinality parts $A$ and $S-A$ such that both parts have the same sum and no pair in $P$ has both elements in one side of the partition?

Is this variant of partition problem NP-complete in the strong sense?

It seems, that there exists a pseudo-polynomial time algorithm for your problem.

Denote by $N$ the sum of $S$. Add $N \cdot |S|$ to each element of $S$. This allows us to not carry about the cardinality restriction.

Consider a square boolean table $T$ of size $N^2 \cdot |S|$ with the following sense:

$T(X,Y)=1$ if there exist two disjoint subsets $S_X$ and $S_Y$ of $S$ such that no pair in $P$ has both elements in $S_X$ or in $S_Y$ and $|P \cap (S_X \cup S_Y)| \not= 1$.

Now use standard dynamic programming. First fill all elements of $T$ by $0$.

Fill $T(0,0):=1$. Assume we have filled a part of the table.

Let $a$ be an element of $S$ that we have not considered yet. If $a$ is not element of a pair then fill $T(X + a, Y) = T(X, Y+a)=1$ for all $X$ and $Y$ such that $T(X, Y)=1$.

If $(a,b)$ is a pair then $T(X + a, Y+b) = T(X+b, Y+a)=1$.

After filling all table the answer is the element $T(\frac{N\cdot|S|^2 + N}{2},\frac{N\cdot|S|^2 + N}{2})$

since the all sum now is $N\cdot|S|^2 + N$.

• Let $m$ be the number of pairs $p_i$. So, the two elements in each pair must go into different parts in the final partition. These possibilities can be represented by a binary number $\{0,1\}^m$. I don't see how the dynamic programming algorithm eliminates the need to test all these possibilities. – Mohammad Al-Turkistany Jul 15 '18 at 20:46
• I do not suggest to make a brute force. The idea is the same as in Pseudo-polynomial time algorithm for Subset sum: en.wikipedia.org/wiki/… – Alexey Milovanov Jul 15 '18 at 21:22