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

<p>This is the idea: you can view the <span class="math-container">$2N$</span> integers as nodes of a graph <span class="math-container">$G$</span>, the pairs in <span class="math-container">$P$</span> indentify the edges between the nodes.</p>

<p>Clearly <span class="math-container">$G$</span> 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 <span class="math-container">$A$</span> vs <span class="math-container">$S \setminus A$</span>.</p>

<p>Each connected part <span class="math-container">$H_i$</span> of <span class="math-container">$G$</span> is bipartite <span class="math-container">$H_i = H_i' \cup H_i''$</span>, and you can treat it like a single integer <span class="math-container">$h_i = | \sum  H_i' - \sum H_i''|$</span></p>

<p>Let <span class="math-container">$w_i$</span> 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 <span class="math-container">$H_i$</span> plus <span class="math-container">$N$</span>: </p>

<p><span class="math-container">$w_i = N + |H_i'| - |H_i''|$</span> if <span class="math-container">$\sum  H_i' &gt; \sum H_i''$</span>; </p>

<p><span class="math-container">$w_i = N + |H_i''| - |H_i'|$</span> otherwise.</p>

<p>Let <span class="math-container">$a_1,a_2,...,a_m$</span> be the "isolated" integers.</p>

<p>Let <span class="math-container">$k$</span> be the minimum value such that <span class="math-container">$2^k &gt; \sum h_i + \sum a_j$</span>.</p>

<p>We finally build a Partition problem with the elements:</p>

<p><span class="math-container">$B = \{ a_j + 2^k (N + 1) \} \cup \{ h_i + 2^k w_i \}$</span></p>

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

<p>Very informally: if <span class="math-container">$h_i$</span> is placed on one side, it also carries the <span class="math-container">$w_i$</span> (positive) "weight" that keeps track of the (absolute) difference between the number of elements of <span class="math-container">$H_i'$</span> and <span class="math-container">$H_i''$</span>; 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 <span class="math-container">$A$</span> from <span class="math-container">$B_1$</span>: if <span class="math-container">$h_i$</span> (or <span class="math-container">$a_j$</span>) is placed on <span class="math-container">$B_1$</span> then the integer nodes of the bipartite component <span class="math-container">$H_i$</span> must be arranged in such  a way that <span class="math-container">$A$</span> recieves the elements from <span class="math-container">$H_i'$</span> or <span class="math-container">$H_i''$</span> according to which have the greater sum.</p>

<p>A simple example: given the integers: <span class="math-container">$1,1,2,3,4,7$</span> and the pairs <span class="math-container">$(7,2), (7,3)$</span>, we build the following graph <span class="math-container">$G$</span>:</p>

<p><a href="https://i.sstatic.net/d8L9o.png" rel="nofollow noreferrer"><img src="https://i.sstatic.net/d8L9o.png" alt="enter image description here"></a></p>

<p>We then reduce the connected component to a single number <span class="math-container">$(2,-1)$</span> (for better clarity we use the notation <span class="math-container">$(x,y)$</span> instead of <span class="math-container">$x + 2^k (N + y ))$</span>; and solve the corresponding partition problem.</p>

<p>You can also apply the Partition problem pseudo-polynomial time dynamic programming algorithm  to the set <span class="math-container">$B$</span> to find the solution.</p>

CC BY-SA 4.0
2019-01-10T13:59:07.337Z
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 .
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-01-10T14:46:11.767Z
@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$)
Marzio De Biasi
CC BY-SA 4.0
2019-02-13T14:42:36.067Z
@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.
Marzio De Biasi
CC BY-SA 4.0
2019-02-13T15:04:21.157Z
@MarzioDeBiasi The collection of pairs $P$ is disjoint while your reduction does not guarantee it.
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-02-13T17:34:39.040Z
@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).
Marzio De Biasi
CC BY-SA 4.0
2019-02-13T18:47:20.607Z
@MarzioDeBiasi How about the dependence of $k$ on the input instance?
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-02-13T20:30:26.323Z
@MohammadAl-Turkistany: a quick very loose bound for $k$ is $k \leq 2  \log( max(\{a_i\})) $. For example if $S = \{ 16, 32, 64, 128 \}$ and is given in binary: $ 10000,100000,1000000,10000000$ then $k = 9$ because $2^k > \sum a_i$
Marzio De Biasi
CC BY-SA 4.0
2019-02-14T10:01:12.193Z
@MarzioDeBiasi The puzzling point about your reduction is that the problem seems to  requires two matchings but your reduction captures only one. Since the required partition is balanced then a perfect matching guarantees that the two parts have equal sums and a matching to guarantees the enforcement of the restriction imposed by the collection of pairs $P$. I hope it is clear.
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-02-14T11:56:03.597Z
@MohammadAl-Turkistany: the problem "seems" to requires two matchings, but the pairs that share one or more elements enforce a restriction on how the elements can be distributed. For example if you have the pairs $(1,2), (1,3), (1,4), (4,5)$ then the elements $1,5$ are forced to lay on one side of the partition and $2,3,4$ on the other side so the problem reduces to choosing wether to put $1,5$ on one side or on the other; clearly taking into account the difference of the sets size (2 elements vs 3 elements) that also must be balanced (using the trick of shifting the difference by k bits)
Marzio De Biasi
CC BY-SA 4.0
2019-01-07T20:35:19.443Z
2019-01-09T08:36:13.833Z
2019-01-09T08:36:13.833Z
Marzio De Biasi
<p>One of the NP-complete problems listed in the book by Garey and Johnson is EVEN-ODD-PARTITION:</p>

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

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

<ul>
<li>We choose <span class="math-container">$N=n+1$</span>.</li>
<li>The set <span class="math-container">$S$</span> consists of <span class="math-container">$2a_1,2a_2,\ldots,2a_{2n}$</span> together with the integers <span class="math-container">$a_{2n+1}=a_{2n+2}=1$</span>.</li>
<li>The collection <span class="math-container">$P$</span> consists of all pairs <span class="math-container">$(a_{2i-1},a_{2i})$</span> for <span class="math-container">$i=1,\ldots,n$</span>.</li>
</ul>

<p>Note that <span class="math-container">$0&lt;|P|&lt;n+1$</span>, 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.</p>

<p>Hence your problem is NP-complete.</p>

CC BY-SA 4.0
2019-01-06T15:05:48.783Z
I know that it is NP-complete. The post asking whether it is STRONGLY NP-complete or not.
Mohammad Al-Turkistany
CC BY-SA 4.0
2019-01-06T14:39:07.687Z
2019-01-06T14:39:07.687Z
Alexis
<p>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. </p>

<p><a href="https://en.wikipedia.org/wiki/Partition_problem" rel="noreferrer">Partition problem</a> is weakly NP-complete problem since it has pseudo-polynomial time algorithm. I am interested in variants that are strongly NP-complete.</p>

<p>Here is a variant of partition problem:</p>

<p>Restricted partition problem</p>

<p><strong>Input</strong>: Set <span class="math-container">$S$</span> of <span class="math-container">$2N$</span> integers, and a collection <span class="math-container">$P$</span> of pairs from <span class="math-container">$S$</span>, <span class="math-container">$0 \lt |P| \lt N$</span> </p>

<p><strong>Query</strong>: Is there a partition of <span class="math-container">$S$</span> into two equal cardinality parts <span class="math-container">$A$</span> and <span class="math-container">$S-A$</span> such that both parts have the same sum and no pair in <span class="math-container">$P$</span> has both elements in one side of the partition?</p>

<blockquote>
  <p>Is this variant of partition problem NP-complete in the strong sense? </p>
</blockquote>

<p>This was posted first on <a href="https://mathoverflow.net/questions/306039/is-this-partition-problem-strongly-np-complete">Math overflow</a> (I believe the posted answer is incorrect since the proposed dynamic programming algorithm does not take into consideration the cardinality of <span class="math-container">$P$</span>).</p>

CC BY-SA 4.0
2019-02-03T21:36:17.483Z
Can pairs have intersections or are they always disjoint? Also, any reason for assuming |P| < N?
Vinicius dos Santos
<cc.complexity-theory><partition-problem>
Is this partition problem strongly NP-complete?
Mohammad Al-Turkistany
# Is this partition problem strongly NP-complete?

(Asked by: username_0 on 2019-01-06)

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](https://en.wikipedia.org/wiki/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](https://mathoverflow.net/questions/306039/is-this-partition-problem-strongly-np-complete) (I believe the posted answer is incorrect since the proposed dynamic programming algorithm does not take into consideration the cardinality of $P$).

**Tags:** cc.complexity-theory, partition-problem

> **Comments:**
> **username_1**: Can pairs have intersections or are they always disjoint? Also, any reason for assuming |P| < N?  

---

## 2 answers

### Answer by username_2 on 2019-01-07. Score: 3

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](https://i.sstatic.net/d8L9o.png)](https://i.sstatic.net/d8L9o.png)

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.

> **Comments:**
> **username_0**: 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 .  
> **username_2**: @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$)  
> **username_2**: @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.  
> **username_0**: @MarzioDeBiasi The collection of pairs $P$ is disjoint while your reduction does not guarantee it.  
> **username_2**: @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).  
> **username_0**: @MarzioDeBiasi How about the dependence of $k$ on the input instance?  
> **username_2**: @MohammadAl-Turkistany: a quick very loose bound for $k$ is $k \leq 2  \log( max(\{a_i\})) $. For example if $S = \{ 16, 32, 64, 128 \}$ and is given in binary: $ 10000,100000,1000000,10000000$ then $k = 9$ because $2^k > \sum a_i$  
> **username_0**: @MarzioDeBiasi The puzzling point about your reduction is that the problem seems to  requires two matchings but your reduction captures only one. Since the required partition is balanced then a perfect matching guarantees that the two parts have equal sums and a matching to guarantees the enforcement of the restriction imposed by the collection of pairs $P$. I hope it is clear.  
> **username_2**: @MohammadAl-Turkistany: the problem "seems" to requires two matchings, but the pairs that share one or more elements enforce a restriction on how the elements can be distributed. For example if you have the pairs $(1,2), (1,3), (1,4), (4,5)$ then the elements $1,5$ are forced to lay on one side of the partition and $2,3,4$ on the other side so the problem reduces to choosing wether to put $1,5$ on one side or on the other; clearly taking into account the difference of the sets size (2 elements vs 3 elements) that also must be balanced (using the trick of shifting the difference by k bits)  

---

### Answer by username_3 on 2019-01-06. Score: 0

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

> **Comments:**
> **username_0**: I know that it is NP-complete. The post asking whether it is STRONGLY NP-complete or not.  

---

