Theoretical Computer Science
ds.algorithms graph-theory graph-algorithms np-hardness matching
Updated Thu, 23 Jun 2022 17:23:59 GMT

# What is the complexity of this weighted b-edge matching problem?

I'm wondering about the complexity of the following variant of the Generalized Weighted b-edge Matching problem:

Input: An undirected multigraph $$G = (V, E)$$ without loops, an edge partition $$(E_1,E_2)$$ such that $$E_1 \cup E_2 = E$$, capacity functions $$b_l , b_u : V \to \mathbb{N}_0$$, a weight function $$w : E \to \mathbb{N}_0$$ and target integers $$r_1,r_2$$.

Question: Are there subsets of edges $$E_1' \subseteq E_1$$ and $$E_2' \subseteq E_2$$ such that

1. $$\sum_{e\in E_1'} w(e) \geq r_1$$ and $$\sum_{e\in E_2'} w(e) \geq r_2$$; and
2. $$b_l (v) \leq | (E_1' \cup E_2') \cap \delta (v)| \leq b_u(v)$$ holds for each vertex $$v \in V$$ ($$\delta (v)$$ is the set of edges incident to vertex $$v$$)?

Is this problem solvable in polynomial-time or NP-hard?

Without the edge partition we have the standard problem which is solvable in polynomial-time (see Gabow [1] or Anstee [2]). This variant seems to be similar to the Directed Two-Commodity Integral Flow problem which is NP-hard but I couldn't figure out a reduction to this variant.

[1] Gabow, H. N. 1983. An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In Proceedings of the fifteenth annual ACM symposium on Theory of computing, 448456.

[2] Anstee, Richard P. "A polynomial algorithm for b-matchings: an alternative approach." Information Processing Letters 24.3 (1987): 153-157.

## Solution

Assuming $$x(e)=1$$ in Condition 2, the problem is NP-complete.

Clearly it is in NP. We show NP-hardness by reduction from Subset Sum:

Lemma 1. The problem is NP-hard.

Proof. The proof is by the following reduction from Subset Sum. Given a Subset-Sum input $$(y, T)$$, where $$y=(y_1, y_2, \ldots, y_n)$$ is a sequence of integers, and $$T$$ is the target, the reduction outputs the following instance of the problem defined by OP.

For each given integer $$y_i$$, create two new vertices $$v_i$$ and $$v'_i$$, and add two copies of edge $$e_i=(v_i, v'_i)$$, each with weight $$w(e_i) = y_i$$. Put one copy of $$e_i$$ in $$E_1$$ and the other in $$E_2$$, and make $$b_\ell(v_i) = b_u(v_i) = b_\ell(v'_i) = b_u(v'_i) = 1$$. Finally, take $$r_1 = T$$ and $$r_2 = (\sum_i y_i) - T$$. This completes the reduction.

Given any subsequence of $$y$$ that sums to $$T$$, there is a corresponding solution $$(E'_1, E'_2)$$ to the created instance, where, for each $$i$$, if $$y_i$$ is in the subsequence we put the copy of $$e_i$$ that is in $$E_1$$ in $$E'_1$$, and otherwise we put the copy of $$e_i$$ that is in $$E_2$$ in $$E'_2$$. Then each vertex has one chosen edge incident to it, the total weight of edges in $$E'_1$$ is $$T$$, and the total weight of edges in $$E'_2$$ is $$(\sum_i y_i) - T$$, as required.

Conversely, consider any solution $$(E'_1, E'_2)$$ to the created instance. Form a corresponding solution to the Subset-Sum instance by choosing the elements $$y_i$$ of $$y$$ such that $$e_i$$ is in $$E'_1$$. It sums to at least $$T$$ by Condition 1. And it sums to at most $$T$$ because, for each edge $$e_i$$ that is not in $$E'_1$$, it must be that $$e_i$$ is in $$E'_2$$ (by Condition 2), and the total weight of such edges must be at least $$(\sum_i y_i) - T$$ (by Condition 1). $$~~\Box$$