The dissociation number of a graph \(G\) is the number of vertices in a maximum size induced subgraph of \(G\) with vertex degrees at most \(1\). The problem of finding the dissociation number was introduced by Yannakakis, who proved it is NP-hard on the class of bipartite graphs. In this paper, we analyze the dissociation number problem restricted to the class of bipartite graphs in more detail. We strengthen the result of Yannakakis by reducing the problem, in polynomial time, from general bipartite graphs to some particular classes, such as bipartite graphs with maximum degree \(3\) or \(C_4\)-free bipartite graphs. Besides the negative results, we prove that finding the dissociation number is polynomially solvable for bipartite graphs containing no induced subgraph isomorphic to a tree with exactly three vertices of degree \(1\) of distances \(1\), \(2\), and \(3\) from the only vertex of degree \(3\).
The induced matching number of a graph \(G\) is the number of edges in a maximum size induced subgraph of \(G\) with vertex degrees equal to \(1\). Analogous results hold for the induced matching number.
1970-2025 CP (Manitoba, Canada) unless otherwise stated.