__
Revision #1 to TR12-066 | 17th July 2012 05:47
__
#### 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.

Similar to the Tutte's theorem, we derive the determinant criterion

for the existence of a common base (basic matroid parity set) for

linear matroid intersection (linear matroid parity). Moreover, we

prove that if there is a black-box $NC$ algorithm for PIT

(Polynomial Identity Testing), 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).

__
TR12-066 | 22nd April 2012 04:52
__

#### Parallel Complexity for Matroid Intersection and Matroid Parity Problems

**Abstract:**
Let two linear matroids have the same rank in matroid intersection.

A maximum linear matroid intersection (maximum linear matroid parity

set) is called a basic matroid intersection (basic matroid parity

set), if its size is the rank of the matroid. We present that

enumerating all basic matroid intersections (basic matroid parity

sets) is in $NC^2$, provided that there are polynomial bounded basic

matroid intersections (basic matroid parity sets). For the graphic

matroids, We show that constructing all basic matroid intersections

is in $NC^2$ if the number of basic graphic matroid intersections is

polynomial bounded. To our knowledge, these algorithms are the first

deterministic $NC$-algorithms for matroid intersection and matroid

parity. Our result also answers a question of Harvey \cite{HAR}.