In matching theory it is a basic problem to determine all the edges in a given graph which can be extended to a maximum matching. Such edges are called maximally-matchable or allowed edges. In addition to its theoretical relevance this question has application in anonymity problems in databases and certain propagation methods in constraint programming. In the last years researchers from graph theory as well as from the above applications fields developed efficient polynomial time algorithms for the identification of allowed edges, but from practicalpo int of view only the bipartite solution is satisfactory for larger scale problems. While the bipartite case can be easily solved in linear time with respect to the number of edges, the complexity gap with the nonbipartite case is significant: a magnitude of the number of vertices.

In this talk first we will review the methods from the literature for determining the maximally-matchable edges. Then a decomposition theory based on the matching structure is presented with showing the related algorithmic concept for identifying the allowed edges. Finally we will show that a fixed-parameter linear time divide-and-conquer algorithm can be worked out for non-bipartite graphs, where the complexity of the new method will be expressed with the help of a graph parameter arising from the developed decomposition structure.

The talk is based on a joint work with Radoslaw Cymer (Augsburg).