Ширина клики

В теории графов кликовая ширина графа $G — это параметр$ , который описывает структурную сложность графа; она тесно связана с шириной дерева , но в отличие от ширины дерева может быть маленькой для плотных графов . Оно определяется как минимальное количество меток, необходимых для построения $G$ с помощью следующих 4 операций:

Создание новой вершины $v$ с меткой $i$ (обозначается $i (v)$ )
Дизъюнктное объединение двух помеченных графов $G$ и $H$ (обозначается ) $G\oplus H$
Соединение ребром каждой вершины, помеченной $i,$ с каждой вершиной, помеченной $j$ (обозначаемой $η (i, j)$ ), где $i \neq j$
Переименование метки $i$ в метку $j$ (обозначается $ρ (i, j)$ )

Графы ограниченной кликовой ширины включают кографы и дистанционно-наследственные графы . Хотя вычислить ширину клики, когда она неограничена, NP-трудно , и неизвестно, можно ли ее вычислить за полиномиальное время , когда она ограничена, известны эффективные алгоритмы аппроксимации ширины клики. На основе этих алгоритмов и теоремы Курселя многие задачи оптимизации графов, которые являются NP-трудными для произвольных графов, могут быть решены или быстро аппроксимированы на графах ограниченной кликовой ширины.

Последовательности построения, лежащие в основе концепции ширины клики, были сформулированы Курселем , Энгельфритом и Розенбергом в 1990 году ^[1] и Ванке (1994). Название «ширина клики» использовалось Хлебиковой (1992) для другой концепции. К 1993 году этот термин уже имел свое нынешнее значение. ^[2]

Специальные классы графов

Кографы - это в точности графы с кликовой шириной не более 2. ^[3] Каждый дистанционно-наследственный граф имеет кликовую ширину не более 3. Однако кликовая ширина графов с единичными интервалами неограничена (в зависимости от их сеточной структуры). ^[4] Точно так же ширина клики двудольных графов перестановок неограничена (на основе аналогичной структуры сетки). ^[5] На основе характеристики кографов как графов без индуцированного подграфа, изоморфного пути с четырьмя вершинами, была классифицирована кликовая ширина многих классов графов, определяемых запрещенными индуцированными подграфами. ^[6]

Другие графы с ограниченной шириной клика включают степени k- листов для ограниченных значений $k$ ; это индуцированные подграфы листьев дерева $T$ в $степени$ графа $Tk$ . Однако листовые степени с неограниченными показателями не имеют ограниченной кликовой ширины. ^[7]

Границы

Курсель и Олариу (2000) и Корней и Ротикс (2005) доказали следующие оценки ширины клики некоторых графов:

Если граф имеет кликовую ширину не более $k$ , то же самое имеет и каждый индуцированный подграф графа. ^[8]
Граф дополнений графа кликовой ширины $k$ имеет кликовую ширину не более $2 k$ . ^[9]
Графы древовидной ширины $w$ имеют кликовую ширину не более $3 \cdot 2 w - 1$ . Экспоненциальная зависимость в этой оценке необходима: существуют графы, кликовая ширина которых экспоненциально превышает ширину их дерева. ^[10] С другой стороны, графы ограниченной кликовой ширины могут иметь неограниченную древовидную ширину; например, полные графы с $n$ -вершинами имеют ширину клики 2, но ширину дерева $n$ $- 1$ . Однако графы кликовой ширины $k$ , не имеющие полного двудольного графа $K$ $t$ $,$ $t$ в качестве подграфа, имеют древовидную ширину не более $3$ $k$ $($ $t$ $- 1) - 1$ . Следовательно, для каждого семейства разреженных графов ограниченная ширина дерева эквивалентна ограниченной ширине клики. ^[11]
Другой параметр графа, Rank-width , ограничен в обоих направлениях шириной клики: Rank-width ≤ clique-width ≤ 2 ^{Rank-width + 1} . ^[12]

Кроме того, если граф $G$ имеет кликовую ширину $k$ , то мощность графа $G c$ имеет кликовую ширину не более $2 kc k$ . ^[13] Хотя существует экспоненциальный разрыв как в оценке ширины клика по ширине дерева, так и в оценке ширины клики степеней графа, эти границы не объединяют друг друга: если граф $G$ имеет древовидную ширину $w$ , то $G c$ имеет ширина клики не более $2(c + 1) w + 1 - 2$ , только одно экспоненциально по ширине дерева. ^[14]

Вычислительная сложность

Нерешенная задача по математике :

Можно ли распознать графы ограниченной кликовой ширины за полиномиальное время?

(еще нерешенные задачи по математике)

Многие задачи оптимизации, NP-трудные для более общих классов графов, могут быть эффективно решены с помощью динамического программирования на графах ограниченной кликовой ширины, если известна последовательность построения этих графов. ^[15]^[16] В частности, каждое свойство графа , которое может быть выражено в монадической логике второго порядка MSO ₁ (форма логики, позволяющая количественно определять наборы вершин), имеет алгоритм линейного времени для графов ограниченной ширины клика, по форме теоремы Курселя . ^[16]

Также возможно найти оптимальные раскраски графов или гамильтоновы циклы для графов ограниченной кликовой ширины за полиномиальное время, когда известна последовательность построения, но показатель многочлена увеличивается с ростом кликовой ширины, и данные теории сложности вычислений показывают что эта зависимость, вероятно, будет необходима. ^[17] Графы ограниченной ширины клики являются $χ$ -ограниченными , что означает, что их хроматическое число не более чем является функцией размера их наибольшей клики. ^[18]

Графы клики шириной три можно распознать и найти для них последовательность построения за полиномиальное время с помощью алгоритма, основанного на расщепленной декомпозиции . ^[19] Для графов с неограниченной кликовой шириной NP -трудно точно вычислить кликовую ширину, а также NP-трудно получить приближение с сублинейной аддитивной ошибкой. ^[20] Однако, когда ширина клика ограничена, можно получить последовательность построения ограниченной ширины (экспоненциально большую, чем фактическая ширина клика) за полиномиальное время, ^[21] в частности, за квадратичное время по числу вершины. ^[22] Остается открытым вопрос, можно ли вычислить точную ширину клики или более точное ее приближение за управляемое время с фиксированными параметрами , можно ли ее вычислить за полиномиальное время для каждой фиксированной границы ширины клики или даже можно ли распознать графы клики шириной четыре за полиномиальное время. ^[20]

Связанные параметры ширины

Теория графов ограниченной ширины клики аналогична теории графов ограниченной ширины дерева , но в отличие от ширины дерева допускает плотные графы . Если семейство графов имеет ограниченную кликовую ширину, то либо оно имеет ограниченную древовидную ширину, либо каждый полный двудольный граф является подграфом графа в семействе. ^[11] Ширина дерева и ширина клики также связаны через теорию линейных графов : семейство графов имеет ограниченную ширину дерева тогда и только тогда, когда их линейные графы имеют ограниченную ширину клика. ^[23]

Графы ограниченной кликовой ширины также имеют ограниченную двойниковую ширину . ^[24]

Примечания