4
$\begingroup$

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?

$\endgroup$

1 Answer 1

1
$\begingroup$

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$.

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Jul 15, 2018 at 20:46
  • $\begingroup$ 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/… $\endgroup$ Jul 15, 2018 at 21:22

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.