The complexity of dissociation set problems in graphs

被引：58

作者：

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

共 67 条

[11] Independent sets in asteroidal triple-free graphs [J].

Broersma, H ;

Kloks, T ;

Kratsch, D ;

Müller, H .

SIAM JOURNAL ON DISCRETE MATHEMATICS, 1999, 12 (02) :276-287

[12] Independent packings in structured graphs [J].

Cameron, K ;

Hell, P .

MATHEMATICAL PROGRAMMING, 2006, 105 (2-3) :201-213

[13] The graphs with maximum induced matching and maximum matching the same size [J].

Cameron, K ;

Walker, T .

DISCRETE MATHEMATICS, 2005, 299 (1-3) :49-55

[14] INDUCED MATCHINGS [J].

CAMERON, K .

DISCRETE APPLIED MATHEMATICS, 1989, 24 (1-3) :97-102

[15] Induced matchings in intersection graphs [J].

Cameron, K .

DISCRETE MATHEMATICS, 2004, 278 (1-3) :1-9

[16] Finding a maximum induced matching in weakly chordal graphs [J].

Cameron, K ;

Sritharan, R ;

Tang, YW .

DISCRETE MATHEMATICS, 2003, 266 (1-3) :133-142

[17] Induced matchings in asteroidal triple-free graphs [J].

Chang, JM .

DISCRETE APPLIED MATHEMATICS, 2003, 132 (1-3) :67-78

[18]

Chlebík M, 2004, LECT NOTES COMPUT SC, V3221, P192

[19]

Cook S. A., 1971, P 3 ANN ACM S THEOR, P151, DOI [DOI 10.1145/800157.805047, 10.1145/800157.805047]

[20] DOMINATION IN CONVEX AND CHORDAL BIPARTITE GRAPHS [J].

DAMASCHKE, P ;

MULLER, H ;

KRATSCH, D .

INFORMATION PROCESSING LETTERS, 1990, 36 (05) :231-236

← 1 2 3 4 5 6 7 →