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

Let $\mathcal{L}$ be a laminar family consists of sets $F_1,\dots ,F_k$. Let $u_1,\dots ,u_k$ to be positive integers. Consider a graph $G=(V,E)$ with a weight function $w:E\to \mathbb{N}$ and capacity function $c:E\to \mathbb{N}$. We are interested in finding a $y\le c$, such that for every $F_i\in \mathcal{L}$, we have ${\sum }_{v\in F_i}{\sum }_{e:v\in e\in E}{y}_e\le u_i$, and ${\sum }_{e\in E}{y}_e{w}_e$ is maximized.

Formally, it is the following integer program.

$$\begin{array}{rlrlr}& \underset{y\in {\mathbb{Z}}^m}{\max }& & \sum _e{w}_e{y}_e& \\ & \text{s.t.}& & \sum _{v\in F_i}\sum _{e:v\in e\in E}{y}_e\le u_i& i\in [k]\\ & & & 0\le y_e\le c_e& \forall e\in E\end{array}$$

This is a generalization of the maximum weight $c$-capacitated $b$-matching problem. Indeed, we can simply set $F_i=\left\{v_i\right\}$ and $u_i=b_i$. However, this problem is actually no more general than the maximum weight $c$-capacitated $b$-matching problem.

Let $A\in {\mathbb{Z}}^{m\times n}$ be a matrix such that ${\sum }_{i=1}^m|A_{i,j}|\le 2$ for every $j$. We call $A$ a bidirected matrix.

The above theorem can be found in [2]. Note that in Schrijver’s book, one requires ${\sum }_{i=1}^m|A_{i,j}|=2$. It is not hard to see the statement still holds even if we have $\le$ 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^{\prime }=F_i\setminus {\bigcup }_{j:F_j⊊F_i}{F}_j$. We also define $C_i$ to be the indices $j$, such that for all $k$, $F_j\subseteq 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={\sum }_{e:v\in e\in E}{y}_e$. We define $z_i={\sum }_{v\in F_i}{x}_v$, which can be transformed to $z_i={\sum }_{v\in F_i^{\prime }}{x}_v+{\sum }_{j\in C_i}{z}_j$. Therefore we obtain the following integer program by directly applying substitutions.

$$\begin{array}{rlrlr}& \underset{x\in {\mathbb{Z}}^n,y\in {\mathbb{Z}}^m,z\in {\mathbb{Z}}^k}{\max }& & \sum _e{w}_e{y}_e& \\ & \text{s.t.}& & \sum _{v\in F_i^{\prime }}{x}_v+\sum _{j\in C_i}{z}_j-z_i=0& i\in [k]\\ & & & \sum _{e:v\in e\in E}{y}_e-x_v=0& \forall v\in V\\ & & & 0\le y_e\le c_e& \forall e\in E\\ & & & 0\le z_i\le u_i& \forall i\in [k]\end{array}$$

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

References