Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR10-194 | 9th December 2010 15:43

Isolation of Matchings via Chinese Remaindering


Authors: Thanh Minh Hoang
Publication: 11th December 2010 13:04
Downloads: 2570


In this paper we investigate the question whether a perfect matching can be isolated by a weighting scheme
using Chinese Remainder Theorem (short: CRT). We give a systematical analysis to a method based on CRT
suggested by Agrawal in a CCC'03-paper
for testing perfect matchings. We show that this desired test-procedure is based on a deterministic
weighting scheme which can be generalized in a natural way to a scheme for isolating a perfect matching in the graph.
Thereby we give a new insight into the
topic about deterministic isolations of perfect matchings by showing necessary and sufficient conditions for a potential isolation.
Moreover, we show that
if the considered weighting scheme by using CRT for
isolating perfect matchings works, then the maximum matching problem
can be solved completely in $NC$. This is a generalization
of the $NC$-algorithm showed in [Hoa10] for the maximum matching problem for bipartite planar graphs.

ISSN 1433-8092 | Imprint