  In 1982, Papadimitriou and Yannakakis introduced the Exact Matching (EM)
problem where given an edge colored graph, with colors red and blue, and an
integer $k$, the goal is to decide whether or not the graph contains a perfect
matching with exactly $k$ red edges. Although they conjectured it to be
$\textbf{NP}$-complete, soon after it was shown to be solvable in randomized
polynomial time in the seminal work of Mulmuley et al., placing it in the
complexity class $\textbf{RP}$. Since then, all attempts at finding a
deterministic algorithm for EM have failed, thus leaving it as one of the few
natural combinatorial problems in $\textbf{RP}$ but not known to be contained
in $\textbf{P}$, and making it an interesting instance for testing the
hypothesis $\textbf{RP}=\textbf{P}$. Progress has been lacking even on very
restrictive classes of graphs despite the problem being quite well known as
evidenced by the number of works citing it.
  In this paper we aim to gain more insight into EM by studying a new
optimization problem we call Top-k Perfect Matching (TkPM) which we show to be
polynomially equivalent to EM. By virtue of being an optimization problem, it
is more natural to approximate TkPM so we provide approximation algorithms for
it. Some of the approximation algorithms rely on a relaxation of EM on
bipartite graphs where the output is required to be a perfect matching with a
number of red edges differing from $k$ by at most $k/2$, which is of
independent interest and generalizes to the Exact Weight Perfect Matching
(EWPM) problem. We also consider parameterized algorithms and show that TkPM
can be solved in FPT time parameterized by $k$ and the independence number of
the graph. This result again relies on new tools developed for EM which are
also of independent interest.
