<p>Assuming <span class="math-container">$x(e)=1$</span> in Condition 2, the problem is NP-complete. </p>

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

<p><strong>Lemma 1.</strong> <em>The problem is NP-hard.</em></p>

<p><em>Proof.</em> The proof is by the following reduction from Subset Sum.  Given a Subset-Sum input <span class="math-container">$(y, T)$</span>, where <span class="math-container">$y=(y_1, y_2, \ldots, y_n)$</span> is a sequence of integers, and <span class="math-container">$T$</span> is the target, the reduction outputs the following instance of the problem defined by OP.</p>

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

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

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

CC BY-SA 4.0
2020-04-02T17:26:20.310Z
2020-04-02T17:26:20.310Z
Neal Young
<p>I'm wondering about the complexity of the following variant of the Generalized Weighted b-edge Matching problem:</p>

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

<p><strong>Question:</strong> Are there subsets of edges <span class="math-container">$E_1' \subseteq E_1$</span> and <span class="math-container">$E_2' \subseteq E_2$</span> such that </p>

<ol>
<li><span class="math-container">$\sum_{e\in E_1'} w(e) \geq r_1$</span> and <span class="math-container">$\sum_{e\in E_2'} w(e) \geq r_2$</span>; and</li>
<li><span class="math-container">$b_l (v) \leq | (E_1' \cup E_2') \cap \delta (v)| \leq b_u(v)$</span> holds for each vertex <span class="math-container">$v \in V$</span> (<span class="math-container">$\delta (v)$</span> is the set of edges incident to vertex <span class="math-container">$v$</span>)?</li>
</ol>

<p>Is this problem solvable in polynomial-time or NP-hard?</p>

<p>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 <a href="https://en.wikipedia.org/wiki/Multi-commodity_flow_problem" rel="nofollow noreferrer">Directed Two-Commodity Integral Flow problem</a> which is NP-hard but I couldn't figure out a reduction to this variant.</p>

<p><em>[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, 448–456.</em></p>

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

CC BY-SA 4.0
2020-04-02T16:57:01.287Z
What is "$x(e)$" in  _"2. $b_l (v) \leq \sum_{e \in (E_1' \cup E_2') \cap \delta (v)} x(e) \leq b_u(v)$ holds for each vertex $v \in V$?"_
Neal Young
CC BY-SA 4.0
2020-04-03T13:33:19.230Z
$x(e)$ is always 1. I have changed the question accordingly.
JohnSnow123
<ds.algorithms><graph-theory><graph-algorithms><np-hardness><matching>
What is the complexity of this weighted b-edge matching problem?
JohnSnow123
# What is the complexity of this weighted b-edge matching problem?

(Asked by: username_0 on 2020-04-01)

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](https://en.wikipedia.org/wiki/Multi-commodity_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, 448–456.*

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

**Tags:** ds.algorithms, graph-theory, graph-algorithms, np-hardness, matching

> **Comments:**
> **username_1**: What is "$x(e)$" in  _"2. $b_l (v) \leq \sum_{e \in (E_1' \cup E_2') \cap \delta (v)} x(e) \leq b_u(v)$ holds for each vertex $v \in V$?"_  
> **username_0**: $x(e)$ is always 1. I have changed the question accordingly.  

---

## 1 answers

### Answer by username_1 on 2020-04-02. Score: 6 | Accepted answer

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$


---

