Ghosh, Sumanta ;
Gurjar, Rohit
Matroid Intersection: A PseudoDeterministic Parallel Reduction from Search to WeightedDecision
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}
}
15.09.2021
Keywords: 

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

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

Issue date: 

2021 
Date of publication: 

15.09.2021 