Число диссоциации

Число диссоциации — характеристика заданного графа ${\displaystyle G}$, равная наибольшему числу вершин в его диссоциациях — подмножествах вершин, порождающих подграф с максимальной степенью 1. Стандартное обозначение — ${\displaystyle \operatorname {diss} G}$.

Задачу вычисления числа диссоциации исследовал Яннакакис^[1][2] в 1981—1982 годы, установив её NP-трудность даже в классе двудольных и планарных графов^[1]. В 2022 году опубликован алгоритм вычисления 4/3-аппроксимации числа диссоциации двудольного графа^[3].

Определение числа диссоциации является специальным случаем (для ${\displaystyle k=1}$) более общей задачи о максимальном ${\displaystyle k}$-зависимом множестве: определить размер наибольшего подмножества ${\displaystyle S}$ вершин графа ${\displaystyle G}$, такого, что порождённый граф ${\displaystyle G[S]}$ имеет максимальную степень ${\displaystyle k}$.

• Mihalis Yannakakis. Node-Deletion Problems on Bipartite Graphs // SIAM J. Comput.. — 1981. — Т. 10, № 2. — С. 310–327. — doi:10.1137/0210022.
• Christos H. Papadimitriou, Mihalis Yannakakis. The complexity of restricted spanning tree problems // J. ACM. — 1982. — Т. 29, № 2. — С. 285–309. — doi:10.1145/322307.322309.
• Seyedmohammadhossein Hosseinian, Sergiy Butenko. An improved approximation for Maximum k-dependent Set on bipartite graphs // Discrete Appl. Math.. — 2022. — Т. 307. — С. 95–101. — doi:10.1016/j.dam.2021.10.015. — arXiv:2110.02487.