Approximability results for the maximum and minimum maximal induced matching problems

• Published in: Discrete optimization 2008-08, Vol.5 (3), p.584-593
• Main Authors: Orlovich, Yury, Finke, Gerd, Gordon, Valery, Zverovich, Igor
• Format: Article
• Language: English
• Subjects: [formula omitted]-completeness; Approximability; Bipartite graph; Combinatorial optimization; Induced matching
• ISSN: 1572-5286; 1873-636X
• DOI: 10.1016/j.disopt.2007.11.010

An induced matching M of a graph G is a set of pairwise non-adjacent edges such that their end-vertices induce a 1-regular subgraph. An induced matching M is maximal if no other induced matching contains M . The Minimum Maximal Induced Matching problem asks for a minimum maximal induced matching in a given graph. The problem is known to be NP -complete. Here we show that, if P ≠ NP , for any ε > 0 , this problem cannot be approximated within a factor of n 1 − ε in polynomial time, where n denotes the number of vertices in the input graph. The result holds even if the graph in question is restricted to being bipartite. For the related problem of finding an induced matching of maximum size ( Maximum Induced Matching), it is shown that, if P ≠ NP , for any ε > 0 , the problem cannot be approximated within a factor of n 1 / 2 − ε in polynomial time. Moreover, we show that Maximum Induced Matching is NP -complete for planar line graphs of planar bipartite graphs.