УДК 519.17
Конструктивная теорема существования, ассоциированная с локальными преобразованиями графов для задачи о независимом множестве
Д. В. Сироткин1, Д. C. Малышев2
| Аннотация | Задача о независимом множестве для заданного графа состоит в том, чтобы найти размер наибольшего множества его попарно несмежных вершин. Известны многочисленные случаи NP-трудности и случаи полиномиальной разрешимости этой задачи. Для установления вычислительного статуса задачи о независимом множестве в рассматриваемом классе графов часто используются локальные преобразования графов. В данной работе рассматривается некоторый класс замен подграфов в графах, причем замены из этого класса изменяют число независимости контролируемым образом. Каждое такое локальное преобразование графов определяется некоторым шаблоном --- совокупностью подмножеств множества. Очевидно, что совокупность должна быть градуируемой. Показывается, что заменяющий подграф существует для любого градуируемого шаблона. |
|---|---|
| Ключевые слова | задача о независимом множестве, локальное преобразование, граф с заданными свойствами |
1Сироткин Дмитрий Валерьевич, стажер-исследователь, лаборатория алгоритмов и технологий анализа сетевых структур,
ФГАОУ ВО "НИУ ВШЭ" (603155, Россия, г. Нижний Новгород, ул. Большая Печерская, д. 25/12);
ORCID: http://orcid.org/0000-0002-2682-9867, dmitriy.v.sirotkin@gmail.com
2Малышев Дмитрий Сергеевич, профессор, кафедра прикладной математики и информатики,
ФГАОУ ВО "НИУ ВШЭ" (603155, Россия, г. Нижний Новгород, ул. Большая Печерская, д. 25/12),
профессор, кафедра алгебры, геометрии и дискретной математики, ФГАОУ ВО <<ННГУ им. Н. И. Лобачевского>> (603950, Россия, г. Нижний Новгород, пр. Гагарина, д. 23);
доктор физико-математических наук, ORCID: http://orcid.org/0000-0001-7529-8233, dsmalyshev@rambler.ru
Цитирование: Сироткин Д. В., Малышев Д. C. Конструктивная теорема существования, ассоциированная с локальными преобразованиями графов для задачи о независимом множестве // Журнал Средневолжского математического общества. 2019. Т. 21, № 2. С. 215–221.
DOI 10.15507/2079-6900.21.201902.215-221
