27.11.2008

This paper develops on one hand deterministic parallel algorithms (deterministic NC) and proves on the other hand AC⁰-hardness of the general matching problem for various degree definable graph classes. General matching belongs to randomized NC² [MVV]. The deterministic parallel status of the general matching problem (NC or NC-hard for P or nothing of both) is unknown. We will prove that the construction of a perfect matching for graphs of an even number of vertices and a minimal degree of |G|/2 can be done in NC². We shall show that the problem of perfect matching restricted to 2-connected graphs of maximal degree 3, regular 2-connected graphs of degree 4, regular graphs of degree 3, and graphs of minimal degree α|G| for α < 1/2 are AC⁰-hard for the general matching problem.