Approximability of the Minimum Maximal Matching Problem in Planar Graphs

Hiroshi NAGAMOCHI  Yukihiro NISHIDA  Toshihide IBARAKI  

IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences   Vol.E86-A   No.12   pp.3251-3258
Publication Date: 2003/12/01
Online ISSN: 
Print ISSN: 0916-8508
Type of Manuscript: PAPER
Category: Graphs and Networks
graph algorithm,  approximation algorithm,  matching,  planar graph,  separator,  

Full Text: PDF>>
Buy this Article

Given an edge-weighted graph G, the minimum maximal matching problem asks to find a minimum weight maximal matching. The problem is known to be NP-hard even if the graph is planar and unweighted. In this paper, we consider the problem in planar graphs. First, we prove a strong inapproximability for the problem in weighted planar graphs. Second, in contrast with the first result, we show that a polynomial time approximation scheme (PTAS) for the problem in unweighted planar graphs can be obtained by a divide-and-conquer method based on the planar separator theorem. For a given ε > 0, our scheme delivers in time a solution with size at most (1 + ε) times the optimal value, where n is the number of vertices in G and α is a constant number.