Maximal matching polytope in trees. (3rd May 2016)

• Record Type: Journal Article
• Authors: Tural, Mustafa Kemal
• Is Part Of: Optimization methods and software. Volume 31:Number 3(2016)
• Page Start: 471
• Page End: 478
• Publication Date: 2016-05-03
• Subjects: graph theory -- matching -- integer programming -- linear programming -- polyhedral combinatorics; 90C05 -- 90C10 -- 90C57 -- 05C05 -- 05C70; Mathematical optimization -- Periodicals; Algorithms -- Periodicals; 519.7
• DOI: 10.1080/10556788.2015.1104679
• Languages: English
• ISSNs: 1055-6788

Abstract

Abstract : 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.