3
$\begingroup$

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, 448–456.

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

$\endgroup$
  • $\begingroup$ 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$?" $\endgroup$ – Neal Young Apr 2 at 16:57
  • $\begingroup$ $x(e)$ is always 1. I have changed the question accordingly. $\endgroup$ – JohnSnow123 Apr 3 at 13:33
5
$\begingroup$

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$

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.