Меню

Главная
Случайная статья
Настройки
Кликовая ширина
Материал из https://ru.wikipedia.org

В теории графов кликовая ширина графа  — это параметр, который описывает структурную сложность графа. Параметр тесно связан с древесной шириной, но, в отличие от древесной ширины, кликовая ширина может быть ограничена даже для плотных графов. Кликовая ширина определяется как минимальное число меток, необходимых для построения с помощью следующих 4 операций
  1. Создание новой вершины v с меткой i (операция i(v))
  2. Несвязное объединение двух размеченных графов G и H (операция )
  3. Соединение ребром каждой вершины с меткой i с каждой вершиной с меткой j (операция (i, j)), где
  4. Переименование метки i в j (операция (i,j))


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

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

Содержание

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

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

Другие графы с ограниченной кликовой шириной — k-степени листьев[англ.] для ограниченных значений

Границы

Курсель и Олариу[5], а также Корнейл и Ротикс[12], дали следующие границы кликовой ширины некоторых графов:
  • Если граф имеет кликовую ширину максимум
  • Дополнение графа с кликовой шириной
  • Графы с древесной шириной
  • Другой параметр графов, ранговая ширина, ограничена в обоих направлениях кликовой шириной: ранговая ширина кликовой ширины 2ранговой ширины + 1 [17].


Кроме того, если граф

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

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

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

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

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

Примечания
  1. Courcelle, Engelfriet, Rozenberg, 1993.
  2. Wanke, 1994.
  3. Chlebkov, 1992.
  4. Courcelle, 1993.
  5. 1 2 Courcelle, Olariu, 2000.
  6. Golumbic, Rotics, 2000.
  7. Brandstdt, Lozin, 2003.
  8. Brandstdt, Dragan, Le, Mosca, 2005.
  9. Brandstdt, Engelfriet, Le, Lozin, 2006.
  10. Brandstdt, Hundt, 2008.
  11. 1 2 Gurski, Wanke, 2009.
  12. Corneil, Rotics, 2005.
  13. Courcelle, Olariu, 2000, с. Corollary 3.3.
  14. Courcelle, Olariu, 2000, с. Theorem 4.1.
  15. Corneil, Rotics, 2005, Усиление — Courcelle, Olariu, 2000, Theorem 5.5.
  16. 1 2 Gurski, Wanke, 2000.
  17. 1 2 Oum, Seymour, 2006.
  18. Todinca, 2003.
  19. Cogis, Thierry, 2005.
  20. 1 2 Courcelle, Makowsky, Rotics, 2000.
  21. Fomin, Golovach, Lokshtanov, Saurabh, 2010.
  22. Corneil at al, 2012.
  23. 1 2 Fellows, Rosamond, Rotics, Szeider, 2009.
  24. Hlinn, Oum, 2008.
  25. Oum, 2009.
  26. Gurski, Wanke, 2007.


Литература
Downgrade Counter