1
$\begingroup$

This is a follow-up to post Perfect matching problem, where nir proved weak NP-completeness.

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

The problem is to decide the existence of a perfect matching with some given cost $C$.

Is this problem strongly NP-complete?

Improve this question
$\endgroup$
3
  • $\begingroup$ Could you please clarify the cost measure? I interpret the current expression to always assign the same cost regardless of the perfect matching chosen, namely the cost of a perfect matching in which the $i$-th item in $L$ is paired with the $i$-th item in $M$, with the cost of each matched edge being the product of the two integers. $\endgroup$
    – j_random_hacker
    Commented Feb 25, 2021 at 12:28
  • 1
    $\begingroup$ each item in $L$ is assigned one item in $M$ (such that the assignment is a perfect matching, or in other words, a bijection). Then they are multiplied together and summed. The indices refer to the perfect matching. That is, in order to do the "matching" we do a permutation on $L$ and $M$ so that the $i$'th elements in them are assigned together $\endgroup$
    – nir shahar
    Commented Feb 25, 2021 at 12:38
  • $\begingroup$ @nirshahar Good interpretation. $\endgroup$
    – Mohammad Al-Turkistany
    Commented Feb 25, 2021 at 12:48

2 Answers 2

Reset to default
0
$\begingroup$

This is not correct It is left for educational value.

Another strong NP-completeness proof is a simple reduction from distinct 3-partition problem.

Distinct 3-partition

Input: A set $X = \{a_1,a_2,\ldots,a_{3n}\}$ of positive distinct integers, and a positive integer $B$ where $\Sigma_{i=1}^{3n} a_i = nB$, and $B/4 < a_i < B/2$, where $1 \le i \le 3n$.

Question: Is there a partition of $X$ into $n$ triples such that the elements in each triple sum to $B$?

The reduction: $L$ is the set $X$, $M=\{1, 1, 1, 2, 2, 2, ..., i, i, i\}$ for $1 \le i \le n$, and $C=\Sigma_{i=1}^{n} i*B= B*n(n+1)/2$

Then the 3-parition instance has a solution if and only if numerical perfect matching has a solution.

Improve this answer
$\endgroup$
0
$\begingroup$

I found an NP-complete problem, Applying a permutation on a sequence with multiplication, that reduces to my problem. The reduction produces an input to my problem where sequence $a_i$ is the set $L$, $M=\{1,2,3, ..., n\}$, and C=x.

This proves that the problem of numerical perfect matching is NP-complete for unbounded input integers.

**Update ** For polynomialy bounded input integers, numerical perfect matching problem can not be NP-complete unless RP=NP.

There is an easy reduction from my problem to exact perfect matching problem which in RP (for polynomialy bounded edge weights) and there is no known deterministic polynomial time algorithm for it.

Exact perfect matching problem

Input: given edge weighted graph and integer w

Question: Is there a perfect matching of weight exactly w

References:

  1. Papadimitriou, Yannakakis, The complexity of restricted spanning tree problems. Journal of the ACM 29(2), 285–309 (1982)

  2. Mulmuley, Vazirani & Vazirani, Matching is as easy as matrix inversion. Combinatorica, volume 7, 105–113 (1987)

Improve this answer
$\endgroup$

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.