An Exact Algorithm for finding Maximum Induced Matching in Subcubic Graphs

2022/01/10 by Gordon Hoi, Hoi, Gordon, Ammar Fathin Sabili +3
Computer Science · #68R10 #Advanced Graph Theory Research #Caching and Content Delivery #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2201.03220

openalex publication_date 2022/01/10 · openalex created_date 2022/04/03 · openalex updated_date 2026/07/28

Abstract

The Maximum Induced Matching problem asks to find the maximum k such that, given a graph G=(V,E), can we find a subset of vertices S of size k for which every vertices v in the induced graph G[S] has exactly degree 1. In this paper, we design an exact algorithm running in O(1.2630ⁿ) time and polynomial space to solve the Maximum Induced Matching problem for graphs where each vertex has degree at most 3. Prior work solved the problem by finding the Maximum Independent Set using polynomial space in the line graph L(G²); this method uses O(1.3139ⁿ) time.

Related

• Maximal induced matchings in triangle-free graphs
• Induced Matchings in Graphs of Bounded Maximum Degree
• Maximum Induced Matching Algorithms via Vertex Ordering Characterizations
• Induced matchings in graphs of degree at most 4
• An O(n) Time Algorithm For Maximum Induced Matching In Bipartite Star₁23-free Graphs