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 TR09-091 | 11th December 2009 10:37

On the Matching Problem for Special Graph Classes

RSS-Feed




Revision #1
Authors: Thanh Minh Hoang
Accepted on: 11th December 2009 10:37
Downloads: 1863
Keywords: 


Abstract:

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



Changes to previous version:

The presentation of the paper has been improved.


Paper:

TR09-091 | 23rd September 2009 12:13

On the Matching Problem for Special Graph Classes





TR09-091
Authors: Thanh Minh Hoang
Publication: 9th October 2009 20:57
Downloads: 1558
Keywords: 


Abstract:

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



ISSN 1433-8092 | Imprint