Том 25, номер 2, 2018 г., Стр. 5-18

УДК 519.178
Алексеев В. Е., Сорочан С. В.
Новые случаи полиномиальной разрешимости задачи о независимом множестве для графов с запрещёнными путями

Аннотация:
Задача о независимом множестве разрешима за полиномиальное время для графов, не содержащих пути $P_k$ при любом фиксированном $k$. Если же запрещается порождённый путь $P_k$, то при $k > 6$ сложностной статус этой задачи неизвестен. Рассматриваются промежуточные случаи, когда запрещён порождённый путь $P_k$ и некоторые его остовные надграфы. Доказывается полиномиальная разрешимость задачи о независимом множестве в следующих случаях: 1) запрещаются надграфы, у которых минимальная степень вершины меньше $k/2$; 2) запрещаются надграфы, у которых дополнительный граф имеет более $k/2$ рёбер; 3) запрещаются надграфы, из которых с помощью операции пересечения графов можно получить $P_k$.
Библиогр. 12.

Ключевые слова: независимое множество, запрещённый подграф, путь, надграф, полиномиальное время.

DOI: 10.17377/daio.2018.25.581

Алексеев Владимир Евгеньевич ¹
Сорочан Сергей Владимирович ¹
1. Нижегородский гос. университет им. Н. И. Лобачевского, ИИТММ,
пр. Гагарина, 23, корп. 6, 603950 Нижний Новгород, Россия
е-mail: aleve@rambler.ru, svs-05@mail.ru

Статья поступила 8 июня 2017 г.
Исправленный вариант — 22 ноября 2017 г.

Литература

[1] Алексеев В. Е. О влиянии локальных ограничений на сложность определения числа независимости графа // Комбинаторно-алгебраические методы в прикладной математике. Горький: Изд-во Горьк. ун-та, 1982. С. 3–13.

[2] Алексеев В. Е. О числе тупиковых независимых множеств в графах из наследственных классов // Комбинаторно-алгебраические методы в дискретной оптимизации. Н. Новгород: Изд-во ННГУ, 1991. С. 5–8.

[3] Алексеев В. Е. Полиномиальный алгоритм для нахождения наибольших независимых множеств в графах без вилок // Дискрет. анализ и исслед. операций. Сер. 1. 1999. Т. 6, № 4. С. 3–19.

[4] Алексеев В. Е., Коробицын Д. В. О сложности некоторых задач на наследственных классах графов // Дискрет. математика. 1992. Т. 4, № 4. С. 34–40.

[5] Малышев Д. С., Сироткин Д. В. Полиномиальная разрешимость задачи о независимом множестве в одном классе субкубических планарных графов // Дискрет. анализ и исслед. операций. 2017. Т. 24, № 3. С. 35–60.

[6] Grzesik A., Klimo$\check{s}$ov$\acute{a}$ T., Pilipczuk Mar., Pilipczuk Mic. Polynomial-time algorithm for maximum weight independent set on $P_6$-free graphs // arXiv.org/abs/1707.05491, 2017.

[7] Hsu W., Ikura Y., Nemhauser G. L. A polynomial algorithm for maximum weighted vertex packing in graphs without long odd cycles // Math. Program. 1981. V. 20. P. 225–232.

[8] Karthick T., Maffray F. Weighted independent sets in classes of $P_6$-free graphs // Discrete Appl. Math. 2016. V. 209. P. 217–226.

[9] Lokshtanov D., Vatshelle M., Villanger Y. Independent set in $P_5$-free graphs in polynomial time // Proc. 25th Annu. ACM-SIAM Symp. Discrete Algorithms (SODA 2014, Portland, Oregon, USA, Jan. 5–7, 2014). Philadelphia, PA: SIAM, 2014. P. 570–581.

[10] Lozin V. V., Monnot J., Ries B. On the maximum independent set problem in subclasses of subcubic graphs // J. Discrete Algorithms. 2015. V. 31. P. 104–112.

[11] Lozin V. V., Mosca R. Independent sets in extension of $2K_2$-free graphs // Discrete Appl. Math. 2005. V. 146. P. 74–80.

[12] Lozin V. V., Rautenbach D. Some results on graphs without long induced paths // Inf. Process. Lett. 2003. V. 88. P. 167–171.