New results on maximum induced matchings in bipartite graphs and beyond

作者：Dabrowski Konrad K^*; Demange Marc; Lozin Vadim V

来源：Theoretical Computer Science, 2013, 478: 33-40.

DOI：10.1016/j.tcs.2013.01.027

• Maximum induced matching
• Fixed-parameter tractability
• Regular bipartite graphs
• Hypercubes

The maximum induced matching problem is known to be APX-hard in the class of bipartite graphs. Moreover, the problem is also intractable in this class from a parameterized point of view, i.e. it is W[1]-hard. In this paper, we reveal several classes of bipartite (and more general) graphs for which the problem admits fixed-parameter tractable algorithms. We also study the computational complexity of the problem for regular bipartite graphs and prove that the problem remains APX-hard even under this restriction. On the other hand, we show that for hypercubes (a proper subclass of regular bipartite graphs) the problem admits a simple solution.

• 出版日期2013-3-25