НЕЗАВИСИМЫЕ МНОЖЕСТВА В ГРАФАХ С ОГРАНИЧЕННЫМИ МИНОРАМИ РАСШИРЕННОЙ МАТРИЦЫ ИНЦИДЕНТНОСТИ
Характеризуются графы, у которых абсолютные величины миноров расширенной матрицы инцидентности ограничены сверху некоторой константой. Доказывается, что при любом фиксированном k задача о независимом множестве решается за полиномиальное время для графов, у которых абсолютные величины миноров матрицы, полученной из матрицы инцидентности добавлением столбца из единиц, не превосходят k.