10-05
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
- MSC:
- 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.