The complexity of dissociation set problems in graphs |
| |
| Authors: | Yury Orlovich Alexandre Dolgui |
| |
| Institution: | a Department of Discrete Mathematics and Algorithmics, Faculty of Applied Mathematics and Computer Science, Belarusian State University, Nezavisimosti Ave. 4, 220030 Minsk, Belarusb Ecole Nationale Supérieure des Mines de Saint Etienne, Centre for Industrial Engineering and Computer Science, 158 cours Fauriel, F-42023 Saint Etienne Cedex 2, Francec Laboratory G-SCOP, University Joseph Fourier, 46 Avenue Félix Viallet, 38031 Grenoble, Franced United Institute of Informatics Problems, National Academy of Sciences of Belarus, 6 Surganova Str., 220012 Minsk, Belaruse Institute of Mathematical Optimization, Otto-von-Guericke University of Magdeburg, Universitätsplatz 2, 39106 Magdeburg, Germany |
| |
| 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. 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. |
| |
| Keywords: | Dissociation set Computational complexity Forbidden induced subgraph Approximability |
| 本文献已被 ScienceDirect 等数据库收录！ |
|
