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

Кографы — это в точности графы с кликовой шириной, не превосходящей двух[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].