<p>This is exactly the (in)famous Exact Matching problem introduced by Papadimitriou &amp; Yannakakis in</p>
<blockquote>
<p>The complexity of restricted spanning tree problems. Journal of the ACM (JACM), 29(2):285–309, 1982.</p>
</blockquote>
<p>The complexity deciding whether a perfect (maximum) matching with exactly k red edges exist, in not known.</p>

CC BY-SA 4.0
2024-07-31T18:48:19.097Z
It is known to be in randomized poly-time.
Chandra Chekuri
CC BY-SA 4.0
2024-07-31T19:41:43.947Z
@ChandraChekuri I think you mean RNC^2 through the Isolation Lemma?
PsySp
CC BY-SA 4.0
2024-07-31T21:22:29.257Z
Obtaining randomized parallel algorithms is one application of the isolation lemma. For the exact matching problem it shows a randomized poly-time algorithm. See arxiv.org/abs/2203.13899  for instance.
Chandra Chekuri
CC BY-SA 4.0
2024-08-10T19:39:10.457Z
So what about the optimization variant that was asked about? You can get a randomized pseudo-polynomial algoritm with standard methods (I believe), but what about the min-cost version with exponentially large weights?
Magnus Wahlström
CC BY-SA 4.0
2024-07-31T17:32:43.163Z
2024-07-31T17:32:43.163Z
PsySp
<p>I'd like to know if the following generalization of min-cost perfect matching is NP-hard.</p>
<p>As usual, we are given a graph <span class="math-container">$G = (V,E)$</span> with costs on edges <span class="math-container">$c: E \to \mathbb{R}_{\geq 0}$</span>. In addition, there is a given set of 'special' edges <span class="math-container">$R \subseteq E$</span> and an integer <span class="math-container">$k$</span>.</p>
<p>The goal is to find the subset of edges <span class="math-container">$F \subseteq E$</span> of minimum cost such that:</p>
<ul>
<li>every vertex has degree 1 in <span class="math-container">$(V,F)$</span>, and</li>
<li>there are exactly <span class="math-container">$k$</span> special edges in <span class="math-container">$F$</span>. That is, <span class="math-container">$|F \cap R| = k$</span>.</li>
</ul>
<p>Is this in <span class="math-container">$P$</span>? Is it NP-hard? Both ;)?</p>

CC BY-SA 4.0
2024-07-31T12:43:39.907Z
It seems that it should be reducible to Exact Weight perfect matching, at least for poly-bounded weights. Perhaps this article is relevant. https://arxiv.org/abs/2203.13899
Chandra Chekuri
<ds.algorithms><graph-theory><graph-algorithms><approximation-algorithms><optimization>
Min-cost perfect matching, but must pick exactly k special edges. Is it NP-hard?
Karagounis Z
# Min-cost perfect matching, but must pick exactly k special edges. Is it NP-hard?

(Asked by: username_0 on 2024-07-31)

I'd like to know if the following generalization of min-cost perfect matching is NP-hard.

As usual, we are given a graph $G = (V,E)$ with costs on edges $c: E \to \mathbb{R}\_{\geq 0}$. In addition, there is a given set of 'special' edges $R \subseteq E$ and an integer $k$.

The goal is to find the subset of edges $F \subseteq E$ of minimum cost such that:

* every vertex has degree 1 in $(V,F)$, and
* there are exactly $k$ special edges in $F$. That is, $|F \cap R| = k$.

Is this in $P$? Is it NP-hard? Both ;)?

**Tags:** ds.algorithms, graph-theory, graph-algorithms, approximation-algorithms, optimization

> **Comments:**
> **username_1**: It seems that it should be reducible to Exact Weight perfect matching, at least for poly-bounded weights. Perhaps this article is relevant. https://arxiv.org/abs/2203.13899  

---

## 1 answers

### Answer by username_2 on 2024-07-31. Score: 4 | Accepted answer

This is exactly the (in)famous Exact Matching problem introduced by Papadimitriou & Yannakakis in

> The complexity of restricted spanning tree problems. Journal of the ACM (JACM), 29(2):285–309, 1982.

The complexity deciding whether a perfect (maximum) matching with exactly k red edges exist, in not known.

> **Comments:**
> **username_1**: It is known to be in randomized poly-time.  
> **username_2**: @ChandraChekuri I think you mean RNC^2 through the Isolation Lemma?  
> **username_1**: Obtaining randomized parallel algorithms is one application of the isolation lemma. For the exact matching problem it shows a randomized poly-time algorithm. See arxiv.org/abs/2203.13899  for instance.  
> **username_3**: So what about the optimization variant that was asked about? You can get a randomized pseudo-polynomial algoritm with standard methods (I believe), but what about the min-cost version with exponentially large weights?  

---

