Affiliation: | aDepartment of Discrete Mathematics and Algorithmics, Faculty of Applied Mathematics and Computer Science, Belarusian State University, Nezavisimosti Ave. 4, 220030 Minsk, Belarus;bInstitute of Computing Science, Poznan University of Technology, ul. Piotrowo 3a, Poznan, Poland;cEcole Nationale Supérieure des Mines de Saint-Etienne, Centre for Industrial Engineering and Computer Science, 158 cours Fauriel, F-42023 Saint Etienne Cedex 2, France;dLaboratoire G-SCOP, Université Joseph Fourier, 46 Avenue Félix Viallet, 38031 Grenoble Cedex, France;eUnited Institute of Informatics Problems, National Academy of Sciences of Belarus, 6 Surganova Str., 220012 Minsk, Belarus |
Abstract: | 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 uv 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 NP-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=NP. |