Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR13-112 | 12th August 2013 11:31

Exact Perfect Matching in Complete Graphs

RSS-Feed




TR13-112
Authors: Rohit Gurjar, Arpita Korwar, Jochen Messner, Thomas Thierauf
Publication: 19th August 2013 23:24
Downloads: 4066
Keywords: 


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.



ISSN 1433-8092 | Imprint