An Exact Algorithm for finding Maximum Induced Matching in Subcubic Graphs

Gordon Hoi, Ammar Fathin Sabili, Frank Stephan

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$…