Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
434723 | Theoretical Computer Science | 2013 | 8 Pages |
Abstract
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.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics