Is this partition problem strongly NP-complete?

Question

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 $P$ of pairs from $S$, $0 \lt |P| \lt N$

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?

This was posted first on Math overflow (I believe the posted answer is incorrect since the proposed dynamic programming algorithm does not take into consideration the cardinality of $P$).

Answer 1

Your problem can be reduced to the Partition problem (which is weakly NP-complete) without an exponential blowup of the numeric values; so your problem is weakly NP-complete, too.

This is the idea: you can view the $2N$ integers as nodes of a graph $G$, the pairs in $P$ indentify the edges between the nodes.

Clearly $G$ cannot contain cycles of odd length (checkable in polynomial time); otherwise there would be a conflict and at least one element should be excluded from the partition $A$ vs $S \setminus A$.

Each connected part $H_i$ of $G$ is bipartite $H_i = H_i' \cup H_i''$, and you can treat it like a single integer $h_i = | \sum H_i' - \sum H_i''|$

Let $w_i$ be the difference between the number of elements in the greatest side and the number of elements in the smallest side of the bipartite component $H_i$ plus $N$:

$w_i = N + |H_i'| - |H_i''|$ if $\sum H_i' > \sum H_i''$;

$w_i = N + |H_i''| - |H_i'|$ otherwise.

Let $a_1,a_2,...,a_m$ be the "isolated" integers.

Let $k$ be the minimum value such that $2^k > \sum h_i + \sum a_j$.

We finally build a Partition problem with the elements:

$B = \{ a_j + 2^k (N + 1) \} \cup \{ h_i + 2^k w_i \}$

It is not hard to show that $B$ has a partition $B = B_1 \cup B_2$, $\sum \{B_1\} = \sum \{B_2\}$ if and only if the original $S$ can be split into two equal size halves having the same sum and such that no pair in $P$ have both elements in the same side.

Very informally: if $h_i$ is placed on one side, it also carries the $w_i$ (positive) "weight" that keeps track of the (absolute) difference between the number of elements of $H_i'$ and $H_i''$; so on the opposite side both the sum and the weight must be "balanced" and this ensures that a solution leads to a valid equal size partition also on the original problem. In the original problem we can derive $A$ from $B_1$: if $h_i$ (or $a_j$) is placed on $B_1$ then the integer nodes of the bipartite component $H_i$ must be arranged in such a way that $A$ recieves the elements from $H_i'$ or $H_i''$ according to which have the greater sum.

A simple example: given the integers: $1,1,2,3,4,7$ and the pairs $(7,2), (7,3)$, we build the following graph $G$:

We then reduce the connected component to a single number $(2,-1)$ (for better clarity we use the notation $(x,y)$ instead of $x + 2^k (N + y ))$; and solve the corresponding partition problem.

You can also apply the Partition problem pseudo-polynomial time dynamic programming algorithm to the set $B$ to find the solution.

Answer 2

One of the NP-complete problems listed in the book by Garey and Johnson is EVEN-ODD-PARTITION:

Problem: EVEN-ODD-PARTITION
Instance: Positive integers $a_1,\ldots,a_{2n}$ with $\sum_{i=1}^{2n}a_i=2A$
Question: Does there exist an index set $I\subseteq\{1,\ldots,2n\}$ that satisfies (i) $\sum_{i\in I}a_i=A$ and (ii) $|I\cap\{2i-1,2i\}|=1$ for all $i=1,\ldots,n$?

Take an arbitrary instance of EVEN-ODD-PARTITION and construct the following instance of your partition problem from it:

• We choose $N=n+1$.
• The set $S$ consists of $2a_1,2a_2,\ldots,2a_{2n}$ together with the integers $a_{2n+1}=a_{2n+2}=1$.
• The collection $P$ consists of all pairs $(a_{2i-1},a_{2i})$ for $i=1,\ldots,n$.

Note that $0<|P|<n+1$, exactly as desired. It is easy to see that the EVEN-ODD-PARTITION instance has answer yes if and only if the newly constructed instance has answer yes.

Hence your problem is NP-complete.