Сложность некоторых задач на графах с ограниченными минорами их матриц ограничений

В статье рассматриваются естественные постановки задач о независимом множестве, о вершинном и о реберном доминирующем множестве как задач целочисленного линейного программирования. Для любого фиксированного $C$ в статье доказывается полиномиальная разрешимость обеих задач о доминирующем множестве в классе графов, у которых все миноры матриц смежности вершин или ребер не превосходят $C$ по абсолютному значению. В статье также доказывается подобный результат для задачи о независимом множестве и класса графов, который задается ограничением абсолютных значений всех миноров матриц, полученных пополнением транспонированных матриц инцидентности векторами из одних единиц.