Title: Parallel algorithms for matroid intersection and matroid parity
Abstract: A maximum linear matroid parity set is called a basic matroid parity set, if its size is the rank of the matroid. We show that determining the existence of a common base (basic matroid parity set) for linear matroid intersection (linear matroid parity) is in NC 2 , provided that there are polynomial number of common bases (basic matroid parity sets). For graphic matroids, we show that finding a common base for matroid intersection is in NC 2 , if the number of common bases is polynomial bounded. To our knowledge, these algorithms are the first deterministic NC algorithms for matroid intersection and matroid parity. We also give a new RNC 2 algorithm that finds a common base for graphic matroid intersection. We prove that if there is a black-box NC algorithm for Polynomial Identity Testing (PIT), then there is an NC algorithm to determine the existence of a common base (basic matroid parity set) for linear matroid intersection (linear matroid parity).
Publication Year: 2015
Publication Date: 2015-05-25
Language: en
Type: article
Indexed In: ['crossref']
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot