Greedy Algorithm for approximation of the Maximum Induced Matching problem in regular graphs of girth at least six
Open Access
Author:
Patel, Chaitanya
Area of Honors:
Computer Science
Degree:
Bachelor of Science
Document Type:
Thesis
Thesis Supervisors:
Piotr Berman, Thesis Supervisor Dr. John Joseph Hannan, Thesis Honors Advisor
Keywords:
Graph Theory Induced Matching Regular graphs Computer Science
Abstract:
An induced matching of a graph G is the edge set of an induced subgraph of G, which is also a matching, i.e., its edge are disjoint. The problem that is discussed in this thesis is the Maximum Induced Matching (MIM for short) problem and its aim is to maximize the size of the matching. The problem has been modeled as the Set Packing and the Maximum Independent Set problem. These problems are very difficult to approximate and for this reason there was extensive research on restricted classes of graphs. The work done in this thesis further improves on a simple linear time greedy algorithm that gives an approximation ratio of d-1 for a d-regular graph. This approximation ratio was improved to 5/3 for d = 3. In this thesis, we further improve this ratio to
be 3/2 from the previous 5/3 for d = 3 (3-regular graphs) under the assumption that the graph has
no cycles of length 5 or less. Moreover, we conjecture that by following a similar methodology
we can generalize the result with the approximation ratio being d=2 for a d-regular graph without
cycles of length smaller than 6.
