¹Department of Informatics, Technological Educational Institute of Athens, 12210 Egaleo , Greece
²Department of Economics, University of Patras, 26500 Rion, Patras, Greece
³Department of Mathematical and Physical Sciences, Aristotle University of Thessaloniki, 54124 Thessaloniki, Greece

---

Abstract—Finding a maximum cardinality matching in a graph is a problem appearing in numerous settings. The problem asks for a set of edges of maximum cardinality, such that no two edges of this set have an endpoint in common. The variety of applications of this problem, along with the fact that several logic predicates can be modelled after it, motivates the study of a related global constraint in the context of Constraint Programming. In this work, we describe a filtering scheme for such a predicate based on matroids. Our method guarantees hyper-arc consistency in polynomial time. It is also applicable to any predicate expressed in terms of an independent system, and remains of polynomial complexity if there exists a polynomial time algorithm for finding a maximum cardinality basis of this independent system. Furthermore, we show that this filtering scheme can be employed to find a maximum cardinality matching.

Index Terms—matching, hyper-arc consistency, matroid intersection

[PDF]

Cite: Dimitris Magos, Ioannis Mourtos, Leonidas Pitsoulis, "The matching predicate and a filtering scheme based on matroids," Journal of Computers vol. 1, no.6, pp. 37-42, 2006.