Zurück zu den Preprints des Jahres 2010


2010-05

On the Complexity and Inapproximability of Dissociation Set Problems in Graphs

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