Is this partition problem strongly NP-complete? 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$).
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' &gt; \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 &gt; \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.