Кликовая ширина

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

1. Создание новой вершины v с меткой i (операция i(v))
2. Несвязное объединение двух размеченных графов G и H (операция ${\displaystyle G\oplus H}$)
3. Соединение ребром каждой вершины с меткой i с каждой вершиной с меткой j (операция η(i, j)), где ${\displaystyle i\neq j}$
4. Переименование метки i в j (операция ρ(i,j))

Построение дистанционно-наследуемуего графа кликовой ширины 3 путём несвязного объединения, переименования вершин и объединения меток. Метки вершин показаны цветом.

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

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

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

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

Другие графы с ограниченной кликовой шириной — k-степени листьев^[англ.] для ограниченных значений k, то есть порождённые подграфы листьев дерева T в степени графа T^k. Однако степень листьев при неограниченном показателе степени не имеет ограниченной ширины листьев^[10][11].

Границы

Курсель и Олариу^[5], а также Корнейл и Ротикс^[12], дали следующие границы кликовой ширины некоторых графов:

• Если граф имеет кликовую ширину максимум k, то то же самое верно для любого порождённого подграфа графа^[13].
• Дополнение графа с кликовой шириной k имеет кликовую ширину, не превосходящую 2k^[14].
• Графы с древесной шириной w имеют кликовую ширину, не превосходящую 3 · 2^{w − 1}. Экспоненциальная зависимость в границе необходима — существуют графы, кликовая ширина которых экспоненционально больше их древесной ширины^[15]. В другом направлении графы с ограниченной кликовой шириной могут иметь неограниченную древесную ширину. Например, полные графы с n вершинами имеют кликовую ширину 2, но древесную ширину n − 1. Графы с кликовой шириной k, однако, не содержащие полного двудольного графа K_t,t в качестве подграфа, имеют древесную ширину, не превосходящую 3k(t − 1) − 1. Таким образом, для любого семейства разреженных графов наличие ограничения древесной ширины эквивалентно наличию ограничения кликовой ширины ^[16].
• Другой параметр графов, ранговая ширина, ограничена в обоих направлениях кликовой шириной: ранговая ширина ≤ кликовой ширины ≤ 2^{ранговой ширины + 1 [17]}.

Кроме того, если граф G имеет кликовую ширину k, то степень графа G^c имеет кликовую ширину, не превосходящую 2kc^k[18]. Хотя в неравенствах для кликовой ширины в сравнениях с древесной шириной и степенью графа присутствует экспонента, эти границы не дают суперпозиции — если граф G имеет древесную ширину w, то G^c имеет кликовую ширину, не превосходящую 2(c + 1)^{w + 1} − 2, лишь простая экспонента от древесной ширины^[11].

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

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

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

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

Связь с древесной шириной

Теория графов с ограниченной кликовой шириной имеет сходство с теорией графов с ограниченной древесной шириной, но, в отличие от древесной ширины, допускает плотные графы. Если семейство графов имеет ограниченную кликовую ширину, то оно либо имеет ограниченную древесную ширину, либо любой полный двудольный граф является подграфом какого-либо графа в семействе^[16]. Древесная ширина и кликовая ширина также связаны теорией рёберных графов — семейство графов имеет ограниченную древесную ширину тогда и только тогда, когда их рёберные графы имеют ограниченную кликовую ширину^[26].