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
- $\sum_{e\in E_1'} w(e) \geq r_1$ and $\sum_{e\in E_2'} w(e) \geq r_2$; and
- $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$
External Links
External links referenced by this document: