An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911866913030144 |
|---|---|
| author | Murakami, Hitoshi Yamaguchi, Yutaro |
| author_facet | Murakami, Hitoshi Yamaguchi, Yutaro |
| contents | The exact matching problem is a constrained variant of the maximum matching problem: given a graph with each edge having a weight $0$ or $1$ and an integer $k$, the goal is to find a perfect matching of weight exactly $k$. Mulmuley, Vazirani, and Vazirani (1987) proposed a randomized polynomial-time algorithm for this problem, and it is still open whether it can be derandomized. Very recently, El Maalouly, Steiner, and Wulf (2023) showed that for bipartite graphs there exists a deterministic FPT algorithm parameterized by the (bipartite) independence number. In this paper, by extending a part of their work, we propose a deterministic FPT algorithm in general parameterized by the minimum size of an odd cycle transversal in addition to the (bipartite) independence number. We also consider a relaxed problem called the correct parity matching problem, and show that a slight generalization of an equivalent problem is NP-hard. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2405_02829 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems Murakami, Hitoshi Yamaguchi, Yutaro Data Structures and Algorithms Combinatorics The exact matching problem is a constrained variant of the maximum matching problem: given a graph with each edge having a weight $0$ or $1$ and an integer $k$, the goal is to find a perfect matching of weight exactly $k$. Mulmuley, Vazirani, and Vazirani (1987) proposed a randomized polynomial-time algorithm for this problem, and it is still open whether it can be derandomized. Very recently, El Maalouly, Steiner, and Wulf (2023) showed that for bipartite graphs there exists a deterministic FPT algorithm parameterized by the (bipartite) independence number. In this paper, by extending a part of their work, we propose a deterministic FPT algorithm in general parameterized by the minimum size of an odd cycle transversal in addition to the (bipartite) independence number. We also consider a relaxed problem called the correct parity matching problem, and show that a slight generalization of an equivalent problem is NP-hard. |
| title | An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems |
| topic | Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2405.02829 |