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

  • $\begingroup$ Can pairs have intersections or are they always disjoint? Also, any reason for assuming |P| < N? $\endgroup$ Feb 3, 2019 at 21:36

2 Answers 2


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

enter image description here

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.

  • $\begingroup$ Thanks for your answer. I am not sure about the reduction. I don't see how it deals with the case when $P = \epsilon N$ where $\epsilon \gt 0$. Secondly, I see exponentially lagrer integers in the constructed instance . $\endgroup$ Jan 10, 2019 at 13:59
  • $\begingroup$ @MohammadAl-Turkistany: the pairs (which are part of the input, so there is no issue with $N$) are transformed into a graph in polynomial time and each connected component is treated as a single integer in the final Paritition problem. The values of the new integers are $O(N^2)$ in size (don't be fooled by the 2^k because it is smaller than $2^k < 2 * N^2$) $\endgroup$ Jan 10, 2019 at 14:46
  • $\begingroup$ @MohammadAl-Turkistany: what is the exact part/point of the reduction that you think it's not correct, and I'll try to explain it better. $\endgroup$ Feb 13, 2019 at 14:42
  • $\begingroup$ @MarzioDeBiasi The collection of pairs $P$ is disjoint while your reduction does not guarantee it. $\endgroup$ Feb 13, 2019 at 15:04
  • $\begingroup$ @MohammadAl-Turkistany: the reduction starts from the pairs, so if the pairs are disjoint, the graph $G$ is built according to them. Note that the reduction is NOT from PARTITION to your problem (so no pairs are "created"), but it is from your problem to PARTITION. In the reduction the numeric values are increased at most by $n^2$, so if your problem is strongly NP-complete, also PARTITION would be strongly NP-complete (which is not the case). $\endgroup$ Feb 13, 2019 at 17:34

One of the NP-complete problems listed in the book by Garey and Johnson is 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.

  • 2
    $\begingroup$ I know that it is NP-complete. The post asking whether it is STRONGLY NP-complete or not. $\endgroup$ Jan 6, 2019 at 15:05

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.