Greedy Algorithm for approximating maximum induced matching

Open Access
Li, Zhenyao
Graduate Program:
Computer Science and Engineering
Master of Science
Document Type:
Master Thesis
Date of Defense:
July 25, 2014
Committee Members:
  • Piotr Berman, Thesis Advisor
  • Sofya Raskhodnikova, Thesis Advisor
  • graph theory
  • combinatorial problem
  • approximation algorithms
  • induced matching
  • greedy algorithms
An induced matching in a graph G=(V,E) is $M\subseteq E$ such that it is a matching and also the edge set of an induced subgraph G(U). The goal in Maximum Induced Matching (MIM) problem is to maximize the size of M. This problem can be modelled as a special case of Set Packing, or Maximum Independent Set, and, like those problems, it is very hard to approximate, which motivates our focus on restricted classes of graphs. This work improves on the work of Duckworth \EA who showed that MIM is APX-hard even for bipartide 3-regular graphs, while a simple greedy algorithm gives an approximation ratio of d-1 for d-regular graph. We improve this ratio for 3-regular graphs from 2 to 5/3, also using a linear time greedy algorithm. We believe that our new methodology can be applied to other classes of graphs as well. More specifically, we conjecture that for 4-regular graphs it gives an approximation ratio of 7/3, improving on 3.