The complexity of dissociation set problems in graphs

被引：56

作者：

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 条

[31] Complexity of two coloring problems in cubic planar bipartite mixed graphs
Ries, B.
DISCRETE APPLIED MATHEMATICS, 2010, 158 (05) : 592 - 596
[32] Robust maximum weighted independent-set problems on interval graphs
Fabrice Talla Nobibon
Roel Leus
Optimization Letters, 2014, 8 : 227 - 235
[33] More on the complexity of defensive domination in graphs
Henning, Michael A.
Pandey, Arti
Tripathi, Vikash
DISCRETE APPLIED MATHEMATICS, 2025, 362 : 167 - 179
[34] Robust maximum weighted independent-set problems on interval graphs
Nobibon, Fabrice Talla
Leus, Roel
OPTIMIZATION LETTERS, 2014, 8 (01) : 227 - 235
[35] Analysis of the impact of the number of edges in connected graphs on the computational complexity of the independent set problem
Malyshev D.S.
Journal of Applied and Industrial Mathematics, 2012, 6 (1) : 97 - 99
[36] The parameterized complexity of finding secluded solutions to some classical optimization problems on graphs
van Bevern, Rene
Fluschnik, Till
Mertzios, George B.
Molter, Hendrik
Sorge, Manuel
Suchy, Ondrej
DISCRETE OPTIMIZATION, 2018, 30 : 20 - 50
[37] On the parameterized complexity of some optimization problems related to multiple-interval graphs
Jiang, Minghui
THEORETICAL COMPUTER SCIENCE, 2010, 411 (49) : 4253 - 4262
[38] Complexity Results for Matching Cut Problems in Graphs Without Long Induced Paths
Le, Hoang-Oanh
Le, Van Bang
GRAPH-THEORETIC CONCEPTS IN COMPUTER SCIENCE, WG 2023, 2023, 14093 : 417 - 431
[39] Complexity and approximability of extended Spanning Star Forest problems in general and complete graphs
Khoshkhah, Kaveh
Ghadikolaei, Mehdi Khosravian
Monnot, Jerome
Theis, Dirk Oliver
THEORETICAL COMPUTER SCIENCE, 2019, 775 : 1 - 15
[40] On the Parameterized Complexity of Approximating Dominating Set
Karthik, C. S.
Laekhanukit, Bundit
Manurangsi, Pasin
STOC'18: PROCEEDINGS OF THE 50TH ANNUAL ACM SIGACT SYMPOSIUM ON THEORY OF COMPUTING, 2018, : 1283 - 1296

← 1 2 3 4 5 →