The complexity of dissociation set problems in graphs

被引：55

作者：

Orlovich, Yury ^{[1
]}

Dolgui, Alexandre ^{[2
]}

Finke, Gerd ^{[3
]}

Gordon, Valery ^{[4
]}

Werner, Frank ^{[5
]}

机构：

[1] Belarusian State Univ, Fac Appl Math & Comp Sci, Dept Discrete Math & Algorithm, Minsk 220030, BELARUS

[2] Ecole Natl Super Mines, Ctr Ind Engn & Comp Sci, F-42023 St Etienne 2, France

[3] Univ Grenoble 1, Lab G SCOP, F-38031 Grenoble, France

[4] Natl Acad Sci Belarus, United Inst Informat Problems, Minsk 220012, BELARUS

[5] Otto VonGuericke Univ Magdegurg, Inst Math Optimizat, D-39106 Magdeburg, Germany

来源：

DISCRETE APPLIED MATHEMATICS | 2011年 / 159卷 / 13期

关键词：

Dissociation set; Computational complexity; Forbidden induced subgraph; Approximability; MAXIMUM INDUCED MATCHINGS; INDEPENDENT SETS; CLAW-FREE; POLYNOMIAL ALGORITHM; NP-COMPLETENESS; DOMINATING SET; WEIGHT; APPROXIMABILITY; SUBCLASSES; HARDNESS;

D O I：

10.1016/j.dam.2011.04.023

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

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. (C) 2011 Elsevier B.V. All rights reserved.

引用

页码：1352 / 1366

页数：15

共 50 条

[1] On the complexity of the independent set problem in triangle graphs
Orlovich, Yury
Blazewicz, Jacek
Dolgui, Alexandre
Finke, Gerd
Gordon, Valery
DISCRETE MATHEMATICS, 2011, 311 (16) : 1670 - 1680
[2] Complexity of the robust weighted independent set problems on interval graphs
Adam Kasperski
Paweł Zieliński
Optimization Letters, 2015, 9 : 427 - 436
[3] Complexity of the robust weighted independent set problems on interval graphs
Kasperski, Adam
Zielinski, Pawel
OPTIMIZATION LETTERS, 2015, 9 (03) : 427 - 436
[4] More results on the complexity of identifying problems in graphs
Hudry, Olivier
Lobstein, Antoine
THEORETICAL COMPUTER SCIENCE, 2016, 626 : 1 - 12
[5] The complexity of Dominating Set in geometric intersection graphs
de Berg, Mark
Kisfaludi-Bak, Sandor
Woeginger, Gerhard
THEORETICAL COMPUTER SCIENCE, 2019, 769 : 18 - 31
[6] On the complexity of independent dominating set with obligations in graphs
Laforest, Christian
Martinod, Timothee
THEORETICAL COMPUTER SCIENCE, 2022, 904 : 1 - 14
[7] Graphs, Polymorphisms and the Complexity of Homomorphism Problems
Barto, Libor
Kozik, Marcin
Niven, Todd
STOC'08: PROCEEDINGS OF THE 2008 ACM INTERNATIONAL SYMPOSIUM ON THEORY OF COMPUTING, 2008, : 789 - 796
[8] On the complexity of the minimum outer-connected dominating set problem in graphs
Pradhan, D.
JOURNAL OF COMBINATORIAL OPTIMIZATION, 2016, 31 (01) : 1 - 12
[9] The Parameterized Complexity of Dominating Set and Friends Revisited for Structured Graphs
Misra, Neeldhara
Rathi, Piyush
COMPUTER SCIENCE - THEORY AND APPLICATIONS, 2019, 11532 : 299 - 310
[10] Complexity and approximability of the happy set problem
Asahiro, Yuichi
Eto, Hiroshi
Hanaka, Tesshu
Lin, Guohui
Miyano, Eiji
Terabaru, Ippei
THEORETICAL COMPUTER SCIENCE, 2021, 866 : 123 - 144

← 1 2 3 4 5 →