Dissociation number

In the mathematical discipline of graph theory, a subset of vertices in a graph G is called dissociation if it induces a subgraph with maximum degree 1. The number of vertices in a maximum cardinality dissociation set in G is called the dissociation number of G, denoted by diss(G). The problem of computing diss(G) (dissociation number problem) was firstly studied by Yannakakis.^[1]^[2] The problem is NP-hard even in the class of bipartite and planar graphs.^[3]

An algorithm for computing a 4/3-approximation of the dissociation number in bipartite graphs was published in 2022.^[4]

The dissociation number is a special case of the more general Maximum k-dependent Set Problem for $k=1$ . The problem asks for the size of a largest subset $S$ of the vertices of a graph $G$ , so that the induced subgraph $G[S]$ has maximum degree $k$ .

References

Yannakakis, Mihalis (1981). "Node-Deletion Problems on Bipartite Graphs". SIAM J. Comput. 10 (2): 310–327. doi:10.1137/0210022.
Papadimitriou, Christos H.; Yannakakis, Mihalis (1982). "The complexity of restricted spanning tree problems". J. ACM. 29 (2): 285–309. doi:10.1145/322307.322309.
Hosseinian, Seyedmohammadhossein; Butenko, Sergiy (2022). "An improved approximation for Maximum k-dependent Set on bipartite graphs". Discrete Appl. Math. 307: 95–101. arXiv:2110.02487. doi:10.1016/j.dam.2021.10.015.

[1] Yannakakis 1981

[2] Papadimitriou & Yannakakis 1982

[3] Yannakakis 1981

[4] Hosseinian & Butenko 2022

[1]

[2]

[3]

[4]