Abstract
We study the matroid intersection problem from the parallel complexity perspective. Given two matroids over the same ground set, the problem asks to decide whether they have a common base and its search version asks to find a common base, if one exists. Another widely studied variant is the weighted decision version where with the two matroids, we are given small weights on the ground set elements and a target weight W, and the question is to decide whether there is a common base of weight at least W. From the perspective of parallel complexity, the relation between the search and the decision versions is not well understood. We make a significant progress on this question by giving a pseudodeterministic parallel (NC) algorithm for the search version that uses an oracle access to the weighted decision.
The notion of pseudodeterministic NC was recently introduced by Goldwasser and Grossman [Shafi Goldwasser and Ofer Grossman, 2017], which is a relaxation of NC. A pseudodeterministic NC algorithm for a search problem is a randomized NC algorithm that, for a given input, outputs a fixed solution with high probability. In case the given matroids are linearly representable, our result implies a pseudodeterministic NC algorithm (without the weighted decision oracle). This resolves an open question posed by Anari and Vazirani [Nima Anari and Vijay V. Vazirani, 2020].
BibTeX  Entry
@InProceedings{ghosh_et_al:LIPIcs.APPROX/RANDOM.2021.41,
author = {Ghosh, Sumanta and Gurjar, Rohit},
title = {{Matroid Intersection: A PseudoDeterministic Parallel Reduction from Search to WeightedDecision}},
booktitle = {Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021)},
pages = {41:141:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772075},
ISSN = {18688969},
year = {2021},
volume = {207},
editor = {Wootters, Mary and Sanit\`{a}, Laura},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/14734},
URN = {urn:nbn:de:0030drops147342},
doi = {10.4230/LIPIcs.APPROX/RANDOM.2021.41},
annote = {Keywords: Linear Matroid, Matroid Intersection, Parallel Complexity, Pseudodeterministic NC}
}
Keywords: 

Linear Matroid, Matroid Intersection, Parallel Complexity, Pseudodeterministic NC 
Collection: 

Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2021) 
Issue Date: 

2021 
Date of publication: 

15.09.2021 