Relating dissociation, independence, and matchings

A dissociation set in a graph is a set of vertices inducing a subgraph of maximum degree at most 1. Computing the dissociation number of a given graph , defined as the order of a maximum dissociation set in , is algorithmically hard even when is restricted to be bipartite. Recently, Hosseinian and Butenko proposed a simple -approximation algorithm for the dissociation number problem in bipartite graphs. Their result relies on the inequality , where is a bipartite graph, is a maximum matching in , and denotes the independence number of . We show that the pairs for which this inequality holds with equality can be recognized efficiently, and that a maximum dissociation set can be determined for them efficiently. The dissociation number of a graph satisfies , where denotes the induced matching number of . We show that deciding whether equals any of the four terms , , , and is NP-hard.