ECCC-Report TR09-091https://eccc.weizmann.ac.il/report/2009/091Comments and Revisions published for TR09-091en-usFri, 11 Dec 2009 10:37:35 +0200
Revision 1
| On the Matching Problem for Special Graph Classes |
Thanh Minh Hoang
https://eccc.weizmann.ac.il/report/2009/091#revision1An even cycle in a graph is called {\em nice} by Lovasz and Plummer in [LP86]
if the graph obtained by deleting all vertices of the cycle has some perfect matching.
In the present paper we prove some new complexity bounds for various versions of problems
related to perfect matchings in graphs with a polynomially bounded number of nice cycles.
We show that
for graphs with a polynomially bounded number
of nice cycles
the perfect matching decision problem is in
$SPL$, it is hard for $FewL$, and the perfect matching construction problem is in $L^{C_=L} \cap \oplus L$.
Furthermore, we significantly improve the best known upper bounds,
proved by Agrawal, Hoang, and Thierauf in the STACS'07-paper [AHT07], for
the polynomially bounded perfect matching problem
by showing that the construction and the counting versions
are in $C_=L \cap \oplus L$ and in $C_=L$, respectively.
Note that $SPL, \oplus L, C_=L$, and $L^{C_=L}$
are contained in $NC^2$.
Moreover, we show
that the problem of computing a maximum matching for bipartite planar graphs is in $L^{C_=L}$.
This solves Open Question 4.7 stated in the STACS'08-paper by Datta, Kulkarni, and Roy [DKR08]
where it is asked
whether computing a maximum matching even for bipartite planar graphs can be done in $NC$.
We also show that the problem of computing a maximum matching for
graphs with a polynomially bounded number of even cycles is in $L^{C_=L}$.
Fri, 11 Dec 2009 10:37:35 +0200https://eccc.weizmann.ac.il/report/2009/091#revision1
Paper TR09-091
| On the Matching Problem for Special Graph Classes |
Thanh Minh Hoang
https://eccc.weizmann.ac.il/report/2009/091In the present paper we show some new complexity bounds for
the matching problem for special graph classes.
We show that for graphs with a polynomially bounded number
of nice cycles, the decision perfect matching problem is in
$SPL$, it is hard for $FewL$, and the construction perfect matching problem is in $AC^0(C_=L) \cap \oplus L$.
We further significantly improve the upper bounds, proved in~\cite{AgrHoaThi07}, for
the polynomially bounded perfect matching problem
by showing that the decision version is in $SPL$, and the construction and the counting version
are in $C_=L \cap \oplus L$. Note that $SPL, \oplus L, C_=L$, and $AC^0(C_=L)$
are contained in $NC^2$.
Furthermore, we show
that the problem of computing a maximum matching for bipartite planar graphs is in $AC^0(C_=L)$.
This is a positive answer to Open Question 4.7 stated in the STACS'08-paper~\cite{DatKulRoy08}
where it is asked
whether computing a maximum matching even for bipartite planar graphs can be done in $NC$.
We also show that the problem of computing a maximum matching for
graphs with a polynomially bounded number of even cycles is in $AC^0(C_=L)$. Fri, 09 Oct 2009 20:57:09 +0200https://eccc.weizmann.ac.il/report/2009/091