We are given two sets of nodes $A$ and $B$ forming a graph where each element $x \in A$ can be connected with an element $y \in B$ with different possible weights. The graph can be explained in two ways.

  1. There are multiple edges possible between elements of $X$ and $Y$ having different weights.

  2. Elements of $A$ can be matched with repeated nodes of elements of $B$ with different edge weights.

Let $E(x)$ be the set of edges involving element x. Then the maximum weight matching problem can be formulated as follows:

Let $x_{ij}$ takes value 1, if edge $(i, j) \in E$ is selected and $w_{ij}$ be weight of edge $(i, j) \in E$.

$$\text{minimize} \sum_{(i, j) \in E} x_{ij}w_{ij}$$ $$\sum_{j \in E(i)}x_{ij} \le 1 \forall i \in A$$ $$\sum_{i \in E(j)}x_{ij} \le 1 \forall j \in B$$ $$x_{ij} = \{0, 1\} \quad \forall (i, j) \in E$$

My question is whether this problem satisfy the total unimodularity condition. If it does, how can we prove it? I know proof for the standard problem where you consider submatrices and find the determinant.

Can we still use network flow algorithms to solve this problem?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.