  In the Exact Matching Problem (EM), we are given a graph equipped with a
fixed coloring of its edges with two colors (red and blue), as well as a
positive integer $k$. The task is then to decide whether the given graph
contains a perfect matching exactly $k$ of whose edges have color red. EM
generalizes several important algorithmic problems such as perfect matching and
restricted minimum weight spanning tree problems. When introducing the problem
in 1982, Papadimitriou and Yannakakis conjectured EM to be
$\textbf{NP}$-complete. Later however, Mulmuley et al.~presented a randomized
polynomial time algorithm for EM, which puts EM in $\textbf{RP}$. Given that to
decide whether or not $\textbf{RP}=\textbf{P}$ represents a big open challenge
in complexity theory, this makes it unlikely for EM to be
$\textbf{NP}$-complete, and in fact indicates the possibility of a
deterministic polynomial time algorithm. EM remains one of the few natural
combinatorial problems in $\textbf{RP}$ which are not known to be contained in
$\textbf{P}$, making it an interesting instance for testing the hypothesis
$\textbf{RP}=\textbf{P}$. Despite EM being quite well-known, attempts to devise
deterministic polynomial algorithms have remained illusive during the last 40
years and progress has been lacking even for very restrictive classes of input
graphs. In this paper we finally push the frontier of positive results forward
by proving that EM can be solved in deterministic polynomial time for input
graphs of bounded independence number, and for bipartite input graphs of
bounded bipartite independence number. This generalizes previous positive
results for complete (bipartite) graphs which were the only known results for
EM on dense graphs.
