Том 30, номер 1, 2023 г., Стр. 85-109

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

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

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

DOI: 10.33048/daio.2023.30.752

Сорочан Сергей Владимирович ¹
1. Нижегородский гос. университет им. Н. И. Лобачевского,
пр. Гагарина, 23, 603950 Нижний Новгород, Россия
е-mail: sergey.sorochan@itmm.unn.ru

Статья поступила 31 августа 2022 г.
После доработки — 3 ноября 2022 г.
Принята к публикации 3 ноября 2022 г.

Литература

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

[2] Алексеев В. Е., Сорочан С. В. Новые случаи полиномиальной разрешимости задачи о независимом множестве для графов с запрещёнными путями // Дискрет. анализ и исслед. операций. 2018. Т. 25, № 2. С. 5–18.

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

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

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

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

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

[8] Grzesik A., Klimošová T., Pilipczuk Mar., Pilipczuk Mic. Polynomialtime algorithm for maximum weight independent set on $P_6$-free graphs. Ithaca, NY: Cornell Univ., 2017. (Cornell Univ. Libr. e-Print Archive;
arXiv:1707.05491).

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

[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., Rautenbach D. Some results on graphs without long induced paths // Inform. Process. Lett. 2003. V. 88. P. 167–171.

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

[13] Abrishami T., Chudnovsky M., Dibek C., Rzazewski P. Polynomialtime algorithm for maximum independent set in bounded-degree graphs with no long induced claws // Proc. 33rd Annual ACM-SIAM Symp. Discrete Algorithms (Alexandria, VA, USA, Jan. 9–12, 2022). Philadelphia, PA: SIAM,
2022. P. 1448–1470.

[14] Alekseev V. E., Lozin V. V., Malyshev D. S., Milanic M. The maximum independent set problem in planar graphs // Mathematical foundations of computer science 2008. Proc. 33rd Int. Symp. (Torun, Poland, Aug. 25–29, 2008). Heidelberg: Springer, 2008. P. 96–107. (Lect. Notes Comput. Sci.; V. 5162).

[15] Малышев Д. С. Классы субкубических планарных графов, для которых задача о независимом множестве полиномиально разрешима // Дискрет. анализ и исслед. операций. 2013. V. 20, No. 3. P. 26–44.

[16] Lovász L., Plummer M. D. Matching theory. Amsterdam: Norh-Holland, 1986. 544 p. (Ann. Discrete Math.; V. 29).

[17] Minty G. On maximal independent sets of vertices in claw-free graphs // J. Comb. Theory. Ser. B. 1980. V. 28, No. 3. P. 284–304.

[18] Sbihi N. Algorithme de recherche d’un stable de cardinalite maximum dans un graphe sans etoile // Discrete Math. 1980. V. 29, No. 1. P. 53–76. [French].

[19] Емеличев В. А., Мельников О. И., Сарванов В. И., Тышкевич Р. И. Лекции по теории графов. М.: Наука, 1990. 384 с.

[20] 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.

© С. В. Сорочан, 2023