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$ – Vinicius dos Santos Feb 3 at 21:36

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$ – Mohammad Al-Turkistany Jan 6 at 15:05

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$ Correct NP programs must be #P programs, else answers get ignored. Does anyone else think NP is simply equivalent to #P? Sorry for commenting here, but readers here are interested in NP. I have experimental results... $\endgroup$ – daniel pehoushek Jan 9 at 16:05
  • $\begingroup$ @danielpehoushek: if your comment is not pertinent to this answer, why don't you simply ask your doubts on the cs.stackexchange.com (computer science) site? $\endgroup$ – Marzio De Biasi Jan 9 at 16:11
  • $\begingroup$ @MohammadAl-Turkistany : I didn't receive any feedback; the reduction is simple, so it should be correct, unless I'm missing something trivial; do you see a flaw? $\endgroup$ – Marzio De Biasi Jan 10 at 8:10
  • $\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$ – Mohammad Al-Turkistany Jan 10 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$ – Marzio De Biasi Jan 10 at 14:46

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.