Maximal matching polytope in trees


OPTIMIZATION METHODS & SOFTWARE, vol.31, no.3, pp.471-478, 2016 (SCI-Expanded) identifier identifier

  • Publication Type: Article / Article
  • Volume: 31 Issue: 3
  • Publication Date: 2016
  • Doi Number: 10.1080/10556788.2015.1104679
  • Journal Indexes: Science Citation Index Expanded (SCI-EXPANDED), Scopus
  • Page Numbers: pp.471-478
  • Keywords: graph theory, matching, integer programming, linear programming, polyhedral combinatorics, 90C05, 90C10, 90C57, 05C05, 05C70, EDGE DOMINATING SETS, GRAPHS, POLYHEDRON
  • Middle East Technical University Affiliated: Yes


Given a weighted simple graph, the minimum weighted maximal matching (MWMM) problem is the problem of finding a maximal matching of minimum weight. The MWMM problem is NP-hard in general, but is polynomial-time solvable in some special classes of graphs. For instance, it has been shown that the MWMM problem can be solved in linear time in trees when all the edge weights are equal to one. In this paper, we show that the convex hull of the incidence vectors of maximal matchings (the maximal matching polytope) in trees is given by the polytope described by the linear programming relaxation of a recently proposed integer programming formulation. This establishes the polynomial-time solvability of the MWMM problem in weighted trees. The question of whether or not the MWMM problem can be solved in linear time in weighted trees is open.