2026-07-23T06:26:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:7482 2024-03-06T10:40:27Z ddc:004 open_access

Bipartite Perfect Matching in Pseudo-Deterministic NC Goldwasser, Shafi Grossman, Ofer Parallel Algorithms Pseudo-determinism RNC Perfect Matching We present a pseudo-deterministic NC algorithm for finding perfect matchings in bipartite graphs. Specifically, our algorithm is a randomized parallel algorithm which uses poly(n) processors, poly(log n) depth, poly(log n) random bits, and outputs for each bipartite input graph a unique perfect matching with high probability. That is, on the same graph it returns the same matching for almost all choices of randomness. As an immediate consequence we also find a pseudo-deterministic NC algorithm for constructing a depth first search (DFS) tree. We introduce a method for computing the union of all min-weight perfect matchings of a weighted graph in RNC and a novel set of weight assignments which in combination enable isolating a unique matching in a graph. We then show a way to use pseudo-deterministic algorithms to reduce the number of random bits used by general randomized algorithms. The main idea is that random bits can be reused by successive invocations of pseudo-deterministic randomized algorithms. We use the technique to show an RNC algorithm for constructing a depth first search (DFS) tree using only O(log^2 n) bits whereas the previous best randomized algorithm used O(log^7 n), and a new sequential randomized algorithm for the set-maxima problem which uses fewer random bits than the previous state of the art. Furthermore, we prove that resolving the decision question NC = RNC, would imply an NC algorithm for finding a bipartite perfect matching and finding a DFS tree in NC. This is not implied by previous randomized NC search algorithms for finding bipartite perfect matching, but is implied by the existence of a pseudo-deterministic NC search algorithm. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Shafi Goldwasser and Ofer Grossman 2017 Is Part Of LIPIcs, Volume 80, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2017.87 urn:nbn:de:0030-drops-74824 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2017.87 eng https://creativecommons.org/licenses/by/3.0/legalcode