Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR12-066 | 17th July 2012 05:47

Parallel Algorithms for Matroid Intersection and Matroid Parity

RSS-Feed




Revision #1
Authors: Jinyu Huang
Accepted on: 17th July 2012 05:47
Downloads: 3729
Keywords: 


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).


Paper:

TR12-066 | 22nd April 2012 04:52

Parallel Complexity for Matroid Intersection and Matroid Parity Problems





TR12-066
Authors: Jinyu Huang
Publication: 25th May 2012 13:02
Downloads: 3268
Keywords: 


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}.



ISSN 1433-8092 | Imprint