2
$\begingroup$

The assignment problem is to find the minimum weight perfect matching in a weighted bipartite graph. This problem can be solved using the Hungarian algorithm in polynomial time. It is also possible to enumerate assignments one-by-one in increasing order of their weights using methods like Murty's algorithm, where each new enumeration takes polynomial time.

We can assume that there are 2n vertices in the bipartite graph and that the weights on all present edges are non negative integers less than some value k. Missing edges will need a higher weight or infinity.

My questions is, is it possible to find an assignment of a particular weight (that is not minimal), say W, in polynomial time? Naively, if one tries to enumerate assignments, it may take exponential time to find an assignment of weight W since there may be exponentially many assignments of weight less than W.

Further, if it is possible to find an assignment of weight W in polytime, is it possible to enumerate all assignments of weight W, similar to Murty's algorithm?

I know that we can formulate the assignment problem as a linear program

$\min \sum_{i,j} w_{i,j}x_{i,j} $

such that

$\sum_i x_{i,j} =1$
$\sum_j x_{i,j} =1$
$x_{ij} \ge 0$

I am not sure whether we can directly add the constraint
$\sum_{i,j} w_{i,j}x_{i,j} \ge W$
and still obtain integral solutions for $x_{i,j}$s. Thoughts?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ I suggest checking whether the resulting linear program is totally unimodular. If it is, I suspect you can solve it using linear programming, which has polynomial-time algorithms. You could also check whether this can be expressed as an instance of minimum-cost flow or minimum-cost circulation. $\endgroup$
    – D.W. ♦
    Feb 15, 2018 at 23:57
  • $\begingroup$ One possible solution which I'm not very sure of, is to express our problem of finding a perfect matching with weight exactly W as a quadratic program: $\min\,\, (\vec{w}^{T}\vec{x}-W)^{2}$ with the same linear constraints as the original assignment problem. Depending on whether the corresponding matrix is positive definite, we can use the polynomial time ellipsoid algorithm. Any comments on this? $\endgroup$
    – allrtaken
    Feb 16, 2018 at 2:09

1 Answer 1

Reset to default
1
$\begingroup$

The problem becomes NP - Complete when the weights are exponential in the number of variables. This can be shown by a reduction from the subset sum problem described in the paper "Planarizing gadgets for perfect matching do not exist" by Gurjar et al. (link)

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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