Fractional Linear Matroid Matching is in quasi-NC
<|reference_start|>Fractional Linear Matroid Matching is in quasi-NC: The matching and linear matroid intersection problems are solvable in quasi-NC, meaning that there exist deterministic algorithms that run in polylogarithmic time and use quasi-polynomially many parallel processors. However, such a parallel algorithm is unknown for linear matroid matching, which generalizes both of these problems. In this work, we propose a quasi-NC algorithm for fractional linear matroid matching, which is a relaxation of linear matroid matching and commonly generalizes fractional matching and linear matroid intersection. Our algorithm builds upon the connection of fractional matroid matching to non-commutative Edmonds' problem recently revealed by Oki and Soma~(2023). As a corollary, we also solve black-box non-commutative Edmonds' problem with rank-two skew-symmetric coefficients.<|reference_end|>
@article{gurjar2024fractional,
    title={Fractional Linear Matroid Matching is in quasi-NC},
    author={Rohit Gurjar, Taihei Oki, Roshan Raj},
    journal={arXiv preprint arXiv:2402.18276},
    year={2024},
    archivePrefix={arXiv},
    eprint={2402.18276},
    primaryClass={cs.CC cs.DM cs.DS}
}