Том 24, номер 3, 2017 г., Стр. 35-60

УДК 519.17
Малышев Д. С., Сироткин Д. В.
Полиномиальная разрешимость задачи о независимом множестве в одном классе субкубических планарных графов

Аннотация:
Задача о независимом множестве для заданного обыкновенного графа состоит в вычислении размера наибольшего множества его попарно несмежных вершин. В данной работе доказываем полиномиальную разрешимость этой задачи для субкубических планарных графов, не содержащих порождённого дерева, получаемого отождествлением концов трёх путей длины 3, 3 и 2 соответственно.
Библиогр. 10.

Ключевые слова: задача о независимом множестве, редукция графов, эффективный алгоритм.

DOI: 10.17377/daio.2017.24.549

Малышев Дмитрий Сергеевич ¹
Сироткин Дмитрий Валерьевич ¹
1. Национальный исследовательский университет «Высшая школа экономики»,
ул. Большая Печёрская, 25/12, 603155 Нижний Новгород, Россия
е-mail: dmalishev@hse.ru, dsmalyshev@rambler.ru, dmitriy.v.sirotkin@gmail.com

Статья поступила 25 июля 2016 г.
Исправленный вариант — 12 января 2017 г.

Литература

[1] Алексеев В. Е. О сжимаемых графах // Пробл. кибернетики. 1979. Вып. 36. С. 23–31.

[2] Алексеев В. Е., Лозин В. В. О локальных преобразованиях графов, сохраняющих число независимости // Дискрет. анализ и исслед. операций. 1998. Т. 5, № 1. C. 3–19.

[3] Алексеев В. Е., Малышев Д. С. Классы планарных графов с полиномиально разрешимой задачей о независимом множестве // Дискрет. анализ и исслед. операций. 2008. Т. 15, № 1. C. 3–10.

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

[5] Alekseev V. E. On easy and hard hereditary classes of graphs with respect to the independent set problem // Discrete Appl. Math. 2003. Vol. 132, No. 1–3. P. 17–26.

[6] Alekseev V. E., Lozin V. V., Malyshev D. S., Milanic M. The maximum independent set problem in planar graphs // Proc. 33th Int. Symp. Mathematical Foundations of Computer Science (Torun, August 25–29, 2008). Heidelberg: Springer-Verl., 2008. P. 96–107. (Lect. Notes Comput. Sci.; Vol. 5162)

[7] Hopcroft J., Tarjan R. E. Efficient planarity testing // J. Assoc. Comput. Machinery. 1974. Vol. 21, No. 4.
P. 549–568.

[8] Lozin V. V., Milanic M. Maximum independent sets in graphs of low degree // Proc. 18th Annu. ACM-SIAM Symp. Discrete Algorithms (New Orleans, Jan. 7–9, 2007). Philadelphia, PA: SIAM, 2007. P. 874–880.

[9] Lozin V. V., Milanic M. On the maximum independent set problem in subclasses of planar graphs // J. Graph Algorithms Appl. 2010. Vol. 14, No. 2. P. 269–286.

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