Skip to content
This repository was archived by the owner on Oct 22, 2021. It is now read-only.
This repository was archived by the owner on Oct 22, 2021. It is now read-only.

Is the function maximum_weight_maximal_matchingcorrect? #10

Open
@simonschoelly

Description

@simonschoelly

I was looking at this, because I wanted to convert it to Julia v1.0, but I'm not sure this function actually does what it should do.
From my understanding, it tries to solve the following (simplified here) linear program:

Given bipartite graph G with parts |V1| <= |V2|  and weightmap W = {w_ij}

maximize  Sum( x_ij * w_ij  ) where   w_ij > 0   s.t.
(I)   forall i,j     :  x_ij >= 0
(II)  forall i in V1 : Sum(x_ij) == 1 where j in neighbors(G, i)
(III) forall j in V2 : Sum(x_ij) <= 1 where i in neighbors(G, j)

There are two issues:

  1. Now the objective function clearly aims to maximize the total weight. But I don't see why it only does this among the matchings with the largest number of edges. And shouldn't it be called maximum_weight_maximum_matching then? After all, the documentation suggests it looks for a maximum set of edges and not simply a maximal one.

  2. Condition (II) is not possible in all cases (at least for integer solutions). For example there are bipartite graphs with parts of equal size that do not contain a perfect matching, even if the graph is connected and does not have isolated vertices.

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions