1
$\begingroup$

Suppose you are given two sets of integers L and M both having N elements. The problem is to match each number in L to a number in M. Such perfect matching has some cost given by $\sum_{i=1}^{N} l_i*m_i$.

I want to find some perfect matching with some given cost. I suspect that this is hard (i.e. NP-complete). Can you solve it quickly? (find an efficient algorithm).

Here is an example: we have three courses, credit hours are 4, 5, 8. Grade points are 4, 3, 2. A solution is a perfect matching between the lists that result in some given GPA.

For this to be computationally meaningful, the largest grade point and largest credit hour are unbounded.

P.S. Yuval hinted the reduction from Subset sum problem. I am interested in hardness proof of strong NP-completeness.

$\endgroup$
2
  • $\begingroup$ Assuming that subset sum remains hard when you fix the size of the subset, your question is indeed NP-complete. $\endgroup$ – Yuval Filmus Feb 23 at 23:09
  • $\begingroup$ I would be interested in strong NP-COMPLETE proof if it hard. $\endgroup$ – Mohammad Al-Turkistany Feb 23 at 23:13
2
$\begingroup$

This problem is indeed $NP-complete$ as you have suspected. To see this, we will show a reduction from $SubsetSum$.

The reduction

Let $A,s$ be an instance of $SubsetSum$, where $|A|=n$. We will define $L$ as all the numbers in $A$, in addition to another $n$ zeros. For example, if $A= 4, 5, 8$ then $L=4,5,8,0,0,0$.

Now, we define $M$ to be with $2n$ values, such that we have $n$ ones and $n$ zeros.

The target value will be $s$

Proof

Such a perfect matching defines us a subset $A'\in A$, that $a\in A'$ iff $1$ is matched with $a$. Since we have $n$ values in $A$, and we have $n$ ones and $n$ zeros in $M$, then each pair of $(0,1)$ in $M$ can be assigned to every pair $(a, 0)$ where $a\in A$, and thus any $a\in A$ can be matched with either $0$ or $1$, contributing to the total sum either $a$ or $0$. Therefore, there is a perfect match if and only if there is a subset with that sum (as the value of the matching is a sum of the subset $A'$).

$\endgroup$
2
  • $\begingroup$ I recommend you to fill in the precise details of the proof. This is mainly an "outline" of it, describing the reduction and the proof idea $\endgroup$ – nir shahar Feb 23 at 23:15
  • $\begingroup$ In my comment to Yuval I am interested in strong NP-COMPLETENESS $\endgroup$ – Mohammad Al-Turkistany Feb 23 at 23:30

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.