An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems
<|reference_start|>An FPT Algorithm for the Exact Matching Problem and NP-hardness of Related Problems: 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.<|reference_end|>
@article{murakami2024an,
    title={An FPT Algorithm for the Exact Matching Problem and NP-hardness of
  Related Problems},
    author={Hitoshi Murakami and Yutaro Yamaguchi},
    journal={arXiv preprint arXiv:2405.02829},
    year={2024},
    archivePrefix={arXiv},
    eprint={2405.02829},
    primaryClass={cs.DS math.CO}
}