Rohit Gurjar, Arpita Korwar, Jochen Messner, and Thomas Thierauf
Abstract:
A red-blue graph is a graph where every edge is colored either red or blue.
The exact perfect matching problem asks for a perfect matching in a red-blue graph
that has exactly a given number of red edges.
We show that for complete and bipartite complete graphs,
the exact perfect matching problem is logspace equivalent to
the perfect matching problem.
Hence an efficient parallel algorithm for perfect matching would carry over
to the exact perfect matching problem
for this class of graphs.
We also report some progress in extending the result to arbitrary graphs.