ECCC-Report TR12-066https://eccc.weizmann.ac.il/report/2012/066Comments and Revisions published for TR12-066en-usTue, 17 Jul 2012 05:47:44 +0300
Revision 1
| Parallel Algorithms for Matroid Intersection and Matroid Parity |
Jinyu Huang
https://eccc.weizmann.ac.il/report/2012/066#revision1A 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).Tue, 17 Jul 2012 05:47:44 +0300https://eccc.weizmann.ac.il/report/2012/066#revision1
Paper TR12-066
| Parallel Complexity for Matroid Intersection and Matroid Parity Problems |
Jinyu Huang
https://eccc.weizmann.ac.il/report/2012/066Let 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}.Fri, 25 May 2012 13:02:45 +0300https://eccc.weizmann.ac.il/report/2012/066