ISSN 2079-6900 (Print) 
ISSN 2587-7496 (Online)

Middle Volga Mathematical Society Journal

Скачать статью

УДК 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