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: 1050
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: 1133
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