The complexity of dissociation set problems in graphs

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 th...

Full description

Saved in:
Bibliographic Details
Published in:Discrete Applied Mathematics 2011-08, Vol.159 (13), p.1352-1366
Main Authors: Orlovich, Yury, Dolgui, Alexandre, Finke, Gerd, Gordon, Valery, Werner, Frank
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Applied sciences
Approximability
Combinatorics
Combinatorics. Ordered structures
Complexity
Computational complexity
Computer Science
Computer science
control theory
systems
Dissociation set
Exact sciences and technology
Forbidden induced subgraph
Graphs
Inclusions
Information retrieval. Graph
Mathematical analysis
Mathematics
Operations Research
Sciences and techniques of general use
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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. In addition, we describe several polynomially solvable cases for the problem under consideration. One of them deals with the subclass of the so-called chair-free graphs. Furthermore, the related problem of finding a maximal (by inclusion) dissociation set of minimum size in a given graph is studied, and NP-hardness results for this problem, namely for weakly chordal and bipartite graphs, are derived. Finally, we provide inapproximability results for the dissociation set problems mentioned above.
ISSN:0166-218X
1872-6771
DOI:10.1016/j.dam.2011.04.023