Exact algorithms for Maximum Induced Matching

This paper studies exact algorithms for the Maximum Induced Matching problem, in which an n-vertex graph is given and we are asked to find a set of maximum number of edges in the graph such that no pair of edges in the set have a common endpoint or are adjacent by another edge. This problem has applications in many different areas. We give several structural properties of the problem and show that the problem can be solved in O ⁎ ( 1. 4231 n ) time and polynomial space or O ⁎ ( 1. 3752 n ) time and exponential space.

Authors

• Mingyu Xiao
• Huan Tan

Keywords

• Exact algorithms
• Graph algorithms
• Maximum induced matching