Publication at Faculty of Mathematics and Physics |
2000
Abstract
For all sets $R$ of nonnegative integers, we classify as either NP-complete or polynomial-time solvable the problems of deciding whether a given graph has an $R$-independent set.
For all sets $R$ of nonnegative integers, we classify as either NP-complete or polynomial-time solvable the problems of deciding whether a given graph has an $R$-independent set.