Otto-von-Guericke-Universität Magdeburg



On the Complexity and Inapproximability of Dissociation Set Problems in Graphs

by Y. Orlovich, A. Dolgui, G. Finke, V. Gordon, F. Werner


Preprint series: 10-05, Preprints

68Q25 Analysis of algorithms and problem complexity
05C70 Factorization, matching, covering and packing


Abstract: A subset of vertices in a graph is called a dissociation set if it induces a subgraph with a vertex degree of at most 1. The maximum dissociation set problem, i.e., the problem of finding a dissociation set of maximum size in a given graph is known to be NP-hard for bipartite graphs. We show that the maximum dissociation set problem is NP-hard for planar line graphs of planar bipartite graphs. Furthermore, the related problem of finding a maximal (by inclusion) dissociation set of minimum size in a given graph is studied and some NP-hardness results for this problem are derived. Finally, we provide inapproximability results for the above mentioned dissociation set problems.

Keywords: Dissociation set; Computational complexity; Forbidden induced subgraph; Approximability

The author(s) agree, that this abstract may be stored as full text and distributed as such by abstracting services.

Letzte Änderung: 10.02.2016 - Ansprechpartner: Pierre Krenzlin