2022/02/02 by Bock, Felix, Pardey, Johannes, Penso, Lucia D. +1 · 1 citation
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.2202.01004
A dissociation set in a graph is a set of vertices inducing a subgraph of maximum degree at most 1. Computing the dissociation number \rm diss(G) of a given graph G, defined as the order of a maximum dissociation set in G, is algorithmically hard even when G is restricted to be bipartite. Recently, Hosseinian and Butenko proposed a simple (4)/(3)-approximation algorithm for the dissociation number problem in bipartite graphs. Their result relies on the inequality \rm diss(G)≤(4)/(3)α(G-M) implicit in their work, where G is a bipartite graph, M is a maximum matching in G, and α(G-M) denotes the independence number of G-M. We show that the pairs (G,M) 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 G satisfies max\ α(G),2νs(G)\ ≤ \rm diss(G)≤ α(G)+νs(G)≤ 2α(G), where νs(G) denotes the induced matching number of G. We show that deciding whether \rm diss(G) equals any of the four terms lower and upper bounding \rm diss(G) is NP-hard.