<p>Consider the following variant of min-weight perfect matching. We are given a graph <span class="math-container">$G = (V,E)$</span> with non-negative weights on the edges. We are also given a collection of pairs of edges <span class="math-container">$P \subseteq E \times E$</span>.</p>
<p>Each of these pairs represents a pair of edges which are not allowed to be simultaneously included in the solution. In other words, in addition to having degree 1 on every vertex, our matching <span class="math-container">$F \subseteq E$</span> must not include both edges from any pair in <span class="math-container">$P$</span>.</p>
<p>We seek to find a minimum weight solution satisfying these constraints. This problem is NP-hard (see <a href="https://www.sciencedirect.com/science/article/pii/S0305054812002481?casa_token=MmPwfTRYfe0AAAAA:ttq4FXbG5URrlC3AAgI3NcJSm6x_-fWSJ1tTERdPKznI-kQBJ7vTvzpQHZSKaFvYt9p8kFZmkJw" rel="nofollow noreferrer">here</a>). But I am looking for approximation algorithms. Are any known to your knowledge?</p>
<p>I would be happy for any results, even in the case that the conflict graph is a collection of isolated edges.</p>

CC BY-SA 4.0
2024-12-19T01:40:26.867Z
If you allow arbitrary conflict graph then it seems that you can capture maximum weight independent set  (MWIS) as a special case and we cannot approximate MWIS.
Chandra Chekuri
CC BY-SA 4.0
2024-12-19T02:27:19.013Z
If the conflict graph has good approximation for MWIS via certain restricted class of rounding algorithms then one can obtain a similar guarantee when you combine it with the matching constraint. The basic idea is to use contention resolution schemes. I am going to refer to a paper of mine but it is not the right reference for this special case but better than nothing. https://arxiv.org/abs/1105.4593
Chandra Chekuri
<ds.algorithms><graph-algorithms><np-hardness><approximation-algorithms><optimization>
Min cost perfect matching, but with conflicting edge pairs
Karagounis Z
# Min cost perfect matching, but with conflicting edge pairs

(Asked by: username_0 on 2024-12-19)

Consider the following variant of min-weight perfect matching. We are given a graph $G = (V,E)$ with non-negative weights on the edges. We are also given a collection of pairs of edges $P \subseteq E \times E$.

Each of these pairs represents a pair of edges which are not allowed to be simultaneously included in the solution. In other words, in addition to having degree 1 on every vertex, our matching $F \subseteq E$ must not include both edges from any pair in $P$.

We seek to find a minimum weight solution satisfying these constraints. This problem is NP-hard (see [here](https://www.sciencedirect.com/science/article/pii/S0305054812002481?casa_token=MmPwfTRYfe0AAAAA:ttq4FXbG5URrlC3AAgI3NcJSm6x_-fWSJ1tTERdPKznI-kQBJ7vTvzpQHZSKaFvYt9p8kFZmkJw)). But I am looking for approximation algorithms. Are any known to your knowledge?

I would be happy for any results, even in the case that the conflict graph is a collection of isolated edges.

**Tags:** ds.algorithms, graph-algorithms, np-hardness, approximation-algorithms, optimization
> **Comments:**
> **username_1**: If you allow arbitrary conflict graph then it seems that you can capture maximum weight independent set  (MWIS) as a special case and we cannot approximate MWIS.  
> **username_1**: If the conflict graph has good approximation for MWIS via certain restricted class of rounding algorithms then one can obtain a similar guarantee when you combine it with the matching constraint. The basic idea is to use contention resolution schemes. I am going to refer to a paper of mine but it is not the right reference for this special case but better than nothing. https://arxiv.org/abs/1105.4593  

---

## 0 answers

