by Orlovich, Y., Dolgui, A., Finke, G., Gordon, V., Werner, F..
Series: 2010-05, Preprints
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.
Dissociation set; Computational complexity; Forbidden induced subgraph; Approximability