Новые случаи полиномиальной разрешимости задачи о независимом множестве для графов с запрещенными триодами

Новые случаи полиномиальной разрешимости задачи о независимом множестве для графов с запрещенными триодами

Сорочан С. В.
Дискретный анализ и исследование операций, 30, 1, 85-109 (2023)
Скачать статью

УДК 519.178
DOI: 10.33048/daio.2023.30.752

Аннотация:

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

  1. запрещаются триод и все его остовные надграфы с ограниченными степенями вершин;
  2. запрещаются триод и все его остовные надграфы с большим дефицитом (числом рёбер в дополнительном графе);
  3. запрещаются триод и все его надграфы, из которых с помощью операции пересечения графов можно получить этот триод, а в самом графе есть вершина с ограниченной антистепенью.

Библиогр. 20.

Литература:
  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.
Сорочан Сергей Владимирович
  1. Нижегородский гос. университет им. Н. И. Лобачевского,
    пр. Гагарина, 23, 603950 Нижний Новгород, Россия

E-mail: sergey.sorochan@itmm.unn.ru

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

Abstract:

A triode is a tree with three leaves and a single vertex of degree 3. The independent set problem is solvable in polynomial time for graphs that do not contain a triode as a subgraph with any fixed number of vertices. If the induced triode having $k$ vertices is forbidden, then for $k > 5$ the complexity of this problem is unknown. We consider intermediate cases when an induced triode with any fixed number of vertices and some of its spanning supergraphs are forbidden. For an arbitrary triode with a fixed vertex number, we prove the solvability of the independent set problem in polynomial time in the following cases:
1) a triode and all its spanning supergraphs having bounded vertex
degrees are forbidden;
2) a triode and all its spanning supergraphs having large deficit
(the number of edges in the complementary graph) are forbidden;
3) a triode and all its supergraphs from which this triode can be obtained using the graph intersection operation are forbidden, provided the fraph has a vertex with bounded anti-degree.
Bibliogr. 20.

References:
  1. V. E. Alekseev and D. V. Korobitsyn, Complexity of some problems on hereditary classes of graphs, Diskretn. Mat. 4 (4), 34–40 (1992) [Russian].
     
  2. V. E. Alekseev and S. V. Sorochan, New cases of the polynomial solvability of the independent set problem for graphs with forbidden paths, Diskretn. Anal. Issled. Oper. 25 (2), 5–18 (2018) [Russian] [J. Appl. Ind. Math. 12 (2), 213–219 (2018)].
     
  3. V. E. Alekseev, The local restriction effect on the complexity of finding the graph independence number, in Combinatorial and Algebraic Methods in Applied Mathematics (Izd-vo Gorkov. Univ., Gorkiy, 1982), pp. 3–13.
     
  4. V. E. Alekseev, The number of maximal independent sets in graphs from hereditary classes, in Combinatorial and Algebraic Methods in Discrete Optimization (Izd-vo NNGU, Nizhny Novgorod, 1991), pp. 5–8.
     
  5. V. E. Alekseev, A polynomial algorithm for finding the largest independent sets in claw-free graphs, Diskretn. Anal. Issled. Oper., Ser. 1, 6 (4), 3–19 (1999) [Russian].
     
  6. V. V. Lozin and R. Mosca, Independent sets in extension of $2K_2$-free graphs,
    Discrete Appl. Math. 146, 74–80 (2005).
     
  7. D. Lokshantov, M. Vatshelle, and Y. Villanger, Independent set in $P_5$-free graphs in polynomial time, in Proc. 25th Annual ACM-SIAM Symp. Discrete Algorithms, Portland, OR, USA, Jan. 5–7, 2014 (SIAM, Philadelphia, PA, 2014), pp. 570–581.
     
  8. A. Grzesik, T. Klimošová, Mar. Pilipczuk, and Mic. Pilipczuk, Polynomial- time algorithm for maximum weight independent set on $P_6$-free graphs (Cornell Univ., Ithaca, NY, 2017) (Cornell Univ. Libr. e-Print Archive, arXiv:1707.05491).
     
  9. T. Karthick and F. Maffray, Weighted independent sets in classes of $P_6$-free graphs, Discrete Appl. Math. 209, 217–226 (2016).
     
  10. V. V. Lozin, J. Monnot, and B. Ries, On the maximum independent set problem in subclasses of subcubic graphs, J. Discrete Algorithms 31, 104–112 (2015).
     
  11. V. V. Lozin and D. Rautenbach, Some results on graphs without long induced paths, Inform. Process. Lett. 88, 167–171 (2003).
     
  12. D. S. Malyshev and D. V. Sirotkin, Polynomial-time solvability of the independent set problem in a certain class of subcubic planar graphs, Diskretn. Anal. Issled. Oper. 24 (3), 35–60 (2017) [Russian] [J. Appl. Ind. Math. 11 (3), 400–414 (2017)].
     
  13. T. Abrishami, M. Chudnovsky, C. Dibek, and P. Rzazewski, Polynomial-time algorithm for maximum independent set in boundeddegree graphs with no long induced claws, in Proc. 33rd Annual ACM-SIAM Symp. Discrete Algorithms, Alexandria, VA, USA, Jan. 9–12, 2022 (SIAM, Philadelphia, PA, 2022), pp. 1448–1470.
     
  14. V. E. Alekseev, V. V. Lozin, D. S. Malyshev, and M. Milanic, The maximum independent set problem in planar graphs, in Mathematical Foundations of Computer Science 2008 (Proc. 33rd Int. Symp., Torun, Poland, Aug. 25–29, 2008) (Springer, Heidelberg, 2008), pp. 96–107. (Lect. Notes Comput. Sci., Vol. 5162).
     
  15. D. S. Malyshev, Classes of subcubic planar graphs for which the independent set problem is polynomially solvable, Diskretn. Anal. Issled. Oper. 20 (3), 26–44 (2013) [Russian] [J. Appl. Ind. Math. 7 (4), 537–548 (2013)].
     
  16. L. Lovász and M. D. Plummer, Matching Theory (Norh-Holland, Amsterdam, 1986) (Ann. Discrete Math., Vol. 29).
     
  17. G. Minty, On maximal independent sets of vertices in claw-free graphs, J. Comb. Theory, Ser. B, 28 (3), 284–304 (1980).
     
  18. N. Sbihi, Algorithme de recherche d’un stable de cardinalite maximum dans un graphe sans etoile, Discrete Math. 29 (1), 53–76 (1980). [French].
     
  19. V. A. Emelichev, O. I. Melnikov, V. I. Sarvanov, and R. I. Tyshkevich, Lectures on Graph Theory (Nauka, Moscow, 1990 [Russian]; B. I. Wissenschaftsverlag, Mannheim, 1994).
     
  20. W. Hsu, Y. Ikura, and G. L. Nemhauser, A polynomial algorithmfor maximum weighted vertex packing in graphs without long odd cycles, Math. Program. 20, 225–232 (1981).