The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 24 NO.5 / (1995))
Randomness-Optimal Unique Element Isolation with Applicatons to Perfect Matching and Related Problems
Suresh Chari, Pankaj Rohatgi, Aravind Srinivasan,
Pages. 1036-1050
Abstract In this paper, we precisely characterize the randomness compelxity of the unique element isolation problem, a crucial step in the RNC algorithm for perfect matching by Mulmuley, Vazirani, and Vazirani [Combinatorica, 7 (1987), pp. 105-113] and in several other applications. Given a set $S$ and an unknown family $mathcal Fsubseteq 2^S $ with $mid mathcal Fmidleq Z$, we present a scheme for assigning polynomially bounded weights to the elements of $S$ using only $O(log Z+log mid Smid)$ random bits, such that the minimum weight set in $mathcal F$is unique with high probability. This generalizes the solution of Mulmuley, Vazirani, and Vazirani, who use $O(log Z+log n)$ random bits, where $Z$ is any given upper bound on the number of perfect matchings in the input graph. This generalizes the result of Grigoriev and Karpinski [Proc. IEEE Symposium on Foundations of Computer Science, 1987, pp. 166-172], who present an $NC^3$ algorithm when $Z$ is polynomial
and improves the running time in this case. The worst-case randomness complexity of our algorithm is $O(nlog(m/n))$ random
bits improving on the previous bound of $O(mlog n)$. Our scheme also gives randomness-efficient solutions for several problems where unique element isolation is used, such as RNC algorithms for variants of matching and basic problems on linear matroids. We obtain a randomness-efficient random reduction from SAT to USAT, the language of uniquely satisfiable formulas, which can be derandomized in the case of languages in Few $P$ to yield new proofs of the results Few $Psubseteq oplus P$ and Few $Psubseteq C_= P$.
Contents 1. Introduction
2. The generalized isolating lemma
2.1. New isolation scheme
2.2. A lower bound for the isolation problem
3. Applications to matching problems
3.1. Algorithms for matching
3.2. Graphs with a polynomial number of perfect matchings
3.3. Randomness-efficients with no information on $\mid$Mat $(G)\mid$
4. Other applications
4.1. Randomized reductions from SAT to USAT
4.2. Improved parallel randomness complexity for problems on matroids
5. Conclusions and open problems
Key words parallel algorithms, probabilistic algorithms, matching, matroids, random reductions.
Mathmatical Subject Classification 68Q20, 68Q25, 68Q15