Полиномиальная разрешимость задачи о независимом множестве для некоторых наследственных классов графов с логарифмическими и квазилогарифмическими ограничениями на степени

Полиномиальная разрешимость задачи о независимом множестве для некоторых наследственных классов графов с логарифмическими и квазилогарифмическими ограничениями на степени или антистепени вершин

Сорочан С. В.
Дискретный анализ и исследование операций, 32, 4, 191-212 (2025)
Скачать статью

УДК 519.178 
DOI: 10.33048/daio.2025.32.839

Аннотация:

Триод — это дерево, содержащее не более трёх листьев и не более одной вершины степени 3. Задача о наибольшем независимом множестве (ННМ) разрешима за полиномиальное время для графов, не содержащих в качестве подграфа граф, у которого каждая компонента является триодом с любым фиксированным числом вершин. Если же запрещается $k$-вершинный порождённый подграф с триодными компонентами, то при $k > 5$ вопрос о сложности решения этой задачи остаётся открытым. Пусть $F$ — граф, у которого каждая компонента является триодом, т. е. триодный граф. Известно, что если задача о ННМ полиномиально разрешима в классе всех графов, не содержащих $F$ в качестве порождённого подграфа, то она полиномиально разрешима и в классе всех графов, свободных от графа $F + O_s$, получаемого из $F$ добавлением $s$ изолированных вершин. Если же запретить порождённый подграф вида $F + P_2$, где $P_2$ — цепь с двумя вершинами, то полиномиальная разрешимость задачи о ННМ в классе всех графов без порождённых $F + P_2$ доказана только для очень небольшого числа триодных графов $F$, а для подавляющего большинства таких графов $F$ сложностной статус задачи о ННМ в классе графов, свободных от $F +P_2$, остаётся неизвестным. 

В этой статье рассматриваются так называемые графы с логарифмическими ограничениями. Для каждой вершины такого графа выполнено хотя бы одно из следующих трёх условий: 

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

Доказано, что для любого триодного графа $F$ такого, что задача о ННМ полиномиально разрешима в классе графов, свободных от $F$, она остаётся полиномиально разрешимой и для всех графов с логарифмическими ограничениями, свободных от $F + P_2$. Также рассмотрено одно нетривиальное расширение этого множества графов, названное множеством графов с квазилогарифмическими ограничениями, и доказан аналогичный результат для всех таких графов, свободных от $F +P_2$. Предложены полиномиальные алгоритмы для решения задачи о ННМ для графов с логарифмическими и квазилогарифмическими ограничениями, свободных от $F + P_2$, и найдены верхние оценки сложности этих алгоритмов. 

Библиогр. 19.

Литература:
  1. Алексеев В. Е., Коробицын Д. В. О сложности некоторых задач на наследственных классах графов // Дискрет. математика. 1992. Т. 4, № 4. С. 34–40.
     
  2. Алексеев В. Е. О влиянии локальных ограничений на сложность определения числа независимости графа // Комбинаторно-алгебраические методы в прикладной математике. Горький: Изд-во Горьк. ун-та, 1982. С. 3–13.
     
  3. Алексеев В. Е. О числе тупиковых независимых множеств в графах из наследственных классов // Комбинаторно-алгебраические методы в дискретной оптимизации. Н. Новгород: Изд-во ННГУ, 1991. С. 5–8.
     
  4. 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.
     
  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 Annu. 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, 2017. (e-Print Archive / Cornell Univ.; arXiv:1707.05491).
     
  9. Karthick T., Maffray F. Weighted independent sets in classes of P6-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 // Inf. Process. Lett. 2003. V. 88. P. 167–171.
     
  12. Малышев Д. С., Сироткин Д. В. Полиномиальная разрешимость задачи о независимом множестве в одном классе субкубических планарных графов // Дискрет. анализ и исслед. операций. 2017. Т. 24, № 3. С. 35–60.
     
  13. Abrishami T., Chudnovsky M., Dibek C., Rzążewski P. Polynomialtime algorithm for maximum independent set unbounded-degree graphs with no long induced claws // Proc. 2022 Annu. ACM-SIAM Symp. Discrete Algorithms (Alexandria, VA, USA, Jan. 9–12, 2022). Philadelphia, PA: SIAM, 2022. P. 1448–1470. DOI: 10.1137/1.9781611977073.61.
     
  14. Alekseev V. E., Lozin V. V., Malyshev D. S., Milanič M. The maximum independent set problem in planar graphs // Mathematical foundations of computer science 2008. Proc. 33rd Int. Symp. (Toruń, 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. Алексеев В. Е., Сорочан С. В. Новые случаи полиномиальной разрешимости задачи о независимом множестве для графов с запрещёнными путями // Дискрет. анализ и исслед. операций. 2018. Т. 25, № 2. С. 5–18.
     
  17. Сорочан С. В. Новые случаи полиномиальной разрешимости задачи о независимом множестве для графов с запрещёнными триодами // Дискрет. анализ и исслед. операций. 2023. Т. 30, № 1. С. 85–109.
     
  18. Алексеев В. Е., Захарова Д. В. Теория графов. Н. Новгород: Изд-во Нижегор. гос. ун-та, 2018. 118 с.
     
  19. Алексеев В. Е., Таланов В. А. Графы. Модели вычислений. Алгоритмы. Н. Новгород: Изд-во Нижегор. гос. ун-та, 2005. 308 с.

Исследование выполнено за счёт бюджета Нижегородского гос. университета им. Н. И. Лобачевского. Дополнительных грантов на проведение или руководство этим исследованием получено не было.

Сорочан Сергей Владимирович
  1. Нижегородский гос. университет им. Н. И. Лобачевского, 
    пр. Гагарина, 23, 603950 Нижний Новгород, Россия

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

Статья поступила 17 июля 2025 г.
После доработки — 30 июля 2025 г.
Принята к публикации 22 сентября 2025 г.

Abstract:

A triode is a tree with at most three leaves and at most one vertex of degree 3. The maximum independent set (MIS) problem is solvable in polynomial time for graphs that do not contain as a subgraph a graph whose each component is a triode with any fixed number of vertices. If a $k$-vertex induced subgraph with triode components is forbidden, then, for $k > 5$, the question about the solution complexity for this problem remains open. Let $F$ be a graph whose each component is a triode, that is a triode graph. It is known that, if the MIS problem is polynomially solvable in the class of all graphs not containing $F$ as an induced subgraph, then the problem is also polynomially solvable in the class of all graphs free of $F + O_s$. The graph $F + O_s$ is obtained from $F$ by adding s isolated vertices. If we forbid $F + P_2$ as an induced subgraph and $P_2$ is a path with two vertices, then the polynomial solvability of the MIS problem in the class of all graphs free of $F + P_2$ is proved only for a very small number of triode graphs $F$ while, for the vast majority of such graphs $F$, the complexity status of the MIS problem in the class of ($F + P_2$)-free graphs remains unknown. 

In this article so-called logarithmic constraint graphs are considered. Each vertex in such a graph satisfies at least one of the following three conditions: 

  1. the degree of a vertex does not exceed (up to a multiplicative constant) the logarithm of the total number of vertices in the graph; 
  2. the relative degree of a vertex (that is the maximum number of vertices adjacent to it such that all these adjacent vertices are not adjacent to one of them) does not exceed (up to a multiplicative constant) the logarithm of the total number of vertices in the graph; 
  3. the antidegree of a vertex (that is the number of vertices that are not adjacent to it) does not exceed (up to a multiplicative constant) the logarithm of the total number of vertices in the graph. 

It is proved that, for any triode graph $F$ such that the MIS problem is polynomially solvable in the class of $F$-free graphs, it remains polynomially solvable for all ($F + P_2$)-free graphs with logarithmic constraints. We also consider one non-trivial extension of the latter graph set that consists of graphs with quasi-logarithmic constraints. A similar result is proved for all such ($F + P_2$)-free graphs. We propose polynomial algorithms to solve the MIS problem for graphs with logarithmic and quasi-logarithmic constraints which are free of $F + P_2$, and upper bounds for the algorithm complexity are found. 

Bibliogr. 19.

References:
  1. V. E. Alekseev and D. V. Korobitsyn, On the complexity of some problems on hereditary classes of graphs, Diskretn. Mat. 4 (4), 34–40 (1992) [Russian].
     
  2. V. E. Alekseev, On the influence of local constraints on the complexity of determining the independence number of a graph, in Combinatorial and Algebraic Methods in Applied Mathematics (Izd. Gork. Univ., Gorky, 1982), pp. 3–13 [Russian].
     
  3. V. E. Alekseev, On the number of maximum independent sets in graphs of hereditary classes, in Combinatorial and Algebraic Methods in Discrete Optimization (Izd. NNGU, Nizh. Novgorod, 1991), pp. 5–8 [Russian].
     
  4. G. Minty, On maximal independent sets of vertices in claw-free graphs, J. Comb. Theory, Ser. B, 28 (3), 284–304 (1980).
     
  5. V. E. Alekseev, A polynomial algorithm for finding largest independent sets in fork-free graphs, Diskretn. Anal. Issled. Oper., Ser. 1, 6 (4), 3–19 (1999) [Russian] [Discrete Appl. Math. 135 (1–3), 3–16 (2004)].
     
  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 Annu. 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 (Ithaca, NY, 2017) (e-Print Archive / Cornell Univ., 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, Inf. 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), DOI: ].
     
  13. T. Abrishami, M. Chudnovsky, C. Dibek, and P. Rzążewski, Polynomial-time algorithm for maximum independent set unbounded-degree graphs with no long induced claws, in Proc. 2022 Annu. ACM-SIAM Symp. Discrete Algorithms (Alexandria, VA, USA, Jan. 9–12, 2022) (SIAM, Philadelphia, PA, 2022), pp. 1448–1470, DOI: 10.1137/1.9781611977073.61.
     
  14. V. E. Alekseev, V. V. Lozin, D. S. Malyshev, and M. Milanič, The maximum independent set problem in planar graphs, in Mathematical Foundations of Computer Science 2008, Proc. 33rd Int. Symp. (Toruń, Poland, Aug. 25–29, 2008) (Springer, Heidelberg, 2008), pp. 96–107 (Lect. Notes Comput. Sci., V. 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. 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)].
     
  17. S. V. Sorochan, New cases of polynomial solvability of the independent set problem for graphs with forbidden triodes, Diskretn. Anal. Issled. Oper. 30 (1), 85–109 (2023) [Russian] [J. Appl. Ind. Math. 17 (1) 185–198 (2023)]. 
     
  18. V. E. Alekseev and D. V. Zakharova, Graph Theory (Izd. Nizhegor. Gos. Univ., Nizh. Novgorod, 2018) [Russian]. 
     
  19. V. E. Alekseev and V. A. Talanov, Graphs. Computing Models. Algorithms (Izd. Nizhegor. Gos. Univ., Nizh. Novgorod, 2005) [Russian].