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

**Series:** 2010-05, Preprints

- MSC:
- 68Q25 Analysis of algorithms and problem complexity
- 05C70 Factorization, matching, partitioning, 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