Exact Matching: Correct Parity and FPT Parameterized by Independence Number
share
Given an integer k and a graph where every edge is colored either red or blue, the goal of the exact matching problem is to find a perfect matching with the property that exactly k of its edges are red. Soon after Papadimitriou and Yannakakis introduced the problem in 1982, a randomized polynomial-time algorithm solving the problem was described by Mulmuley et al. Despite a lot of effort, it is still not known today whether a deterministic polynomial-time algorithm exists. This makes the exact matching problem an important candidate to test the popular conjecture that the complexity classes P and RP are equal. In a recent article, progress was made towards this goal by showing that for (bipartite) graphs of bounded (bipartite) independence number, a polynomial time algorithm exists. In terms of parameterized complexity, this algorithm was an XP-algorithm parameterized by the independence number. In this article, we improve the techniques to obtain an FPT-algorithm for bipartite graphs. If the input is a general graph we show that one can at least compute a perfect matching M which has the correct number of red edges modulo 2. This is motivated by our last result, in which we prove that an FPT algorithm for general graphs reduces to the problem of finding in polynomial time a perfect matching M with the correct number of red edges modulo 2 and additionally at most k red edges.
READ FULL TEXT