# Maximum weight hierarchical $b$-matching

We consider the following problem, which appeared in [1].

Let $L$ be a laminar family consists of sets $F_{1},…,F_{k}$. Let $u_{1},…,u_{k}$ to be positive integers. Consider a graph $G=(V,E)$ with a weight function $w:E→N$ and capacity function $c:E→N$. We are interested in finding a $y≤c$, such that for every $F_{i}∈L$, we have $∑_{v∈F_{i}}∑_{e:v∈e∈E}y_{e}≤u_{i}$, and $∑_{e∈E}y_{e}w_{e}$ is maximized.

Formally, it is the following integer program.

$ y∈Z_{m}max s.t. e∑ w_{e}y_{e}v∈F_{i}∑ e:v∈e∈E∑ y_{e}≤u_{i}0≤y_{e}≤c_{e} i∈[k]∀e∈E $

This is a generalization of the maximum weight $c$-capacitated $b$-matching problem. Indeed, we can simply set $F_{i}={v_{i}}$ and $u_{i}=b_{i}$. However, this problem is actually no more general than the maximum weight $c$-capacitated $b$-matching problem.

Let $A∈Z_{m×n}$ be a matrix such that $∑_{i=1}∣A_{i,j}∣≤2$ for every $j$. We call $A$ a bidirected matrix.

Given $A∈Z_{m×n}$ a bidirected matrix and vectors $a,b∈Z_{m}$, $c,d,w∈Z_{n}$. The integer program $max_{x∈Z_{n}}{wx∣a≤Ax≤b,c≤x≤d}$ can be solved in polynomial time. In particular, it is equivalent to the maximum weight $b$-matching problem on graph of size $poly(m,n)$.

The above theorem can be found in [2]. Note that in Schrijver’s book, one requires $∑_{i=1}∣A_{i,j}∣=2$. It is not hard to see the statement still holds even if we have $≤$ in place of $=$.

We will express the maximum weight hierarchical $b$-matching problem as an integer program over
a polytope defined over a bidirected matrix. The integer program is a
modification of the integer program in [3]. The integer program here is simpler,
because we are not trying to reduce to *perfect* $b$-matching.

We define $F_{i}=F_{i}∖⋃_{j:F_{j}⊊F_{i}}F_{j}$. We also define $C_{i}$ to be the indices $j$, such that for all $k$, $F_{j}⊆F_{k}⊊F_{i}$ implies $j=k$. $y_{e}$ denote the amount of capacities we assign to $e$, $x_{v}$ denotes the capacitated degree, hence $x_{v}=∑_{e:v∈e∈E}y_{e}$. We define $z_{i}=∑_{v∈F_{i}}x_{v}$, which can be transformed to $z_{i}=∑_{v∈F_{i}}x_{v}+∑_{j∈C_{i}}z_{j}$. Therefore we obtain the following integer program by directly applying substitutions.

$ x∈Z_{n},y∈Z_{m},z∈Z_{k}max s.t. e∑ w_{e}y_{e}v∈F_{i}∑ x_{v}+j∈C_{i}∑ z_{j}−z_{i}=0e:v∈e∈E∑ y_{e}−x_{v}=00≤y_{e}≤c_{e}0≤z_{i}≤u_{i} i∈[k]∀v∈V∀e∈E∀i∈[k] $

The matrix here is a bidirected matrix. This shows the original problem can be solved in polynomial time.

# References

**Hierarchical b-Matching**, arXiv e-Prints. (2019) arXiv:1904.10210.

**Combinatorial Optimization (3 volume, A, B, & C)**, Springer, 2003.

**On matroid parity and matching polytopes**, Department of Management Science, Lancaster University, 2017.