Maximum Induced Matching Problem on HHD-Free Graphs

We show that the maximum induced matching problem can be solved on hhd-free graphs in O(m2) time; hhd-free graphs generalize chordal graphs and the previous best bound was O(m3). hen, we consider a technique used by Brandstädt and Hoàng (2008) [4] to solve the problem on chordal graphs. Extending this, we show that for a subclass of hhd-free graphs that is more general than chordal graphs the problem can be solved in linear time. We also present examples to demonstrate the tightness of our results. Highlights Faster algorithm to find a largest induced matching in an hhd-free graph is given. For a superclass of chordal graphs, a linear time algorithm for the problem is given. Examples are presented to demonstrate the tightness of results