On the complexity of the independent set problem in triangle graphs

We consider the complexity of the maximum (maximum weight) independent set problem within triangle graphs, i.e., graphs G satisfying the following triangle condition: for every maximal independent set I in G and every edge u v in G − I , there is a vertex w ∈ I such that { u , v , w } is a triangle...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2011-08, Vol.311 (16), p.1670-1680
Main Authors: Orlovich, Yury, Blazewicz, Jacek, Dolgui, Alexandre, Finke, Gerd, Gordon, Valery
Format: Article
Language:English
Subjects:
[formula omitted]-completeness
Algebra
Applied sciences
Approximability
Approximation
Combinatorics
Combinatorics. Ordered structures
Complexity
Computer Science
Computer science
control theory
systems
Exact sciences and technology
Graphs
Independent set
Information retrieval. Graph
Mathematical analysis
Mathematics
Neighborhood set
Operations Research
Sciences and techniques of general use
Theoretical computing
Triangle condition
Triangle graph
Triangles
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:We consider the complexity of the maximum (maximum weight) independent set problem within triangle graphs, i.e., graphs G satisfying the following triangle condition: for every maximal independent set I in G and every edge u v in G − I , there is a vertex w ∈ I such that { u , v , w } is a triangle in G . We also introduce a new graph parameter (the upper independent neighborhood number) and the corresponding upper independent neighborhood set problem. We show that for triangle graphs the new parameter is equal to the independence number. We prove that the problems under consideration are N P -complete, even for some restricted subclasses of triangle graphs, and provide several polynomially solvable cases for these problems within triangle graphs. Furthermore, we show that, for general triangle graphs, the maximum independent set problem and the upper independent neighborhood set problem cannot be polynomially approximated within any fixed constant factor greater than one unless P = N P .
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2011.04.001