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

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

В теории графов кликовая ширина графа  — это параметр, который описывает структурную сложность графа. Параметр тесно связан с древесной шириной, но, в отличие от древесной ширины, кликовая ширина может быть ограничена даже для плотных графов. Кликовая ширина определяется как минимальное число меток, необходимых для построения с помощью следующих 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-степени листьев[англ.] для ограниченных значений k, то есть порождённые подграфы листьев дерева T в степени графа Tk. Однако степень листьев при неограниченном показателе степени не имеет ограниченной ширины листьев[10][11].

Границы[править | править код]

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

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

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

Вычислительная сложность[править | править код]

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

Многие задачи оптимизации, 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. ↑ Chlebíková, 1992.
  4. ↑ Courcelle, 1993.
  5. ↑ 1 2 Courcelle, Olariu, 2000.
  6. ↑ Golumbic, Rotics, 2000.
  7. ↑ Brandstädt, Lozin, 2003.
  8. ↑ Brandstädt, Dragan, Le, Mosca, 2005.
  9. ↑ Brandstädt, Engelfriet, Le, Lozin, 2006.
  10. ↑ Brandstädt, 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. ↑ Hliněný, Oum, 2008.
  25. ↑ Oum, 2009.
  26. ↑ Gurski, Wanke, 2007.

Литература[править | править код]

  • Andreas Brandstädt, F.F. Dragan, H.-O. Le, R. Mosca. New graph classes of bounded clique-width // Theory of Computing Systems. — 2005. — Т. 38. — С. 623–645. — doi:10.1007/s00224-004-1154-6.
  • Andreas Brandstädt, J. Engelfriet, H.-O. Le, V.V. Lozin. Clique-width for 4-vertex forbidden subgraphs // Theory of Computing Systems. — 2006. — Т. 39. — С. 561–590. — doi:10.1007/s00224-005-1199-1.
  • Andreas Brandstädt, Christian Hundt. LATIN 2008: Theoretical informatics. — Springer, Berlin, 2008. — Т. 4957. — С. 479–491. — (Lecture Notes in Comput. Sci.). — doi:10.1007/978-3-540-78773-0_42.
  • Andreas Brandstädt, V.V. Lozin. On the linear structure and clique-width of bipartite permutation graphs // Ars Combinatoria. — 2003. — Т. 67. — С. 273–281.
  • J. Chlebíková. On the tree-width of a graph // Acta Mathematica Universitatis Comenianae. — 1992. — Т. 61, вып. 2. — С. 225–236.
  • O. Cogis, E. Thierry. Computing maximum stable sets for distance-hereditary graphs // Discrete Optimization. — 2005. — Т. 2, вып. 2. — С. 185–188. — doi:10.1016/j.disopt.2005.03.004.
  • Derek G. Corneil, Michel Habib, Jean-Marc Lanlignel, Bruce Reed, Udi Rotics. Polynomial-time recognition of clique-width ≤ 3 graphs // Discrete Applied Mathematics. — 2012. — Т. 160, вып. 6. — С. 834–865. — doi:10.1016/j.dam.2011.03.020..
  • Derek G. Corneil, Udi Rotics. On the relationship between clique-width and treewidth // SIAM Journal on Computing. — 2005. — Т. 34, вып. 4. — С. 825–847. — doi:10.1137/S0097539701385351.
  • Bruno Courcelle, Joost Engelfriet, Grzegorz Rozenberg. Handle-rewriting hypergraph grammars // Journal of Computer and System Sciences. — 1993. — Т. 46, вып. 2. — С. 218–270. — doi:10.1016/0022-0000(93)90004-G.
  • B. Courcelle. Proceedings of Eighth Annual IEEE Symposium on Logic in Computer Science (LICS '93). — 1993. — С. 179–190. — doi:10.1109/LICS.1993.287589.
  • B. Courcelle, J. A. Makowsky, U. Rotics. Linear time solvable optimization problems on graphs on bounded clique width // Theory of Computing Systems. — 2000. — Т. 33, вып. 2. — С. 125–150. — doi:10.1007/s002249910009.
  • B. Courcelle, S. Olariu. Upper bounds to the clique width of graphs // Discrete Applied Mathematics. — 2000. — Т. 101, вып. 1–3. — С. 77–144. — doi:10.1016/S0166-218X(99)00184-5.
  • Michael R. Fellows, Frances A. Rosamond, Udi Rotics, Stefan Szeider. Clique-width is NP-complete // SIAM Journal on Discrete Mathematics. — 2009. — Т. 23, вып. 2. — С. 909–939. — doi:10.1137/070687256.
  • Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh. Intractability of clique-width parameterizations // SIAM Journal on Computing. — 2010. — Т. 39, вып. 5. — С. 1941–1956. — doi:10.1137/080742270..
  • Martin Charles Golumbic, Udi Rotics. On the clique-width of some perfect graph classes // International Journal of Foundations of Computer Science. — 2000. — Т. 11, вып. 3. — С. 423–443. — doi:10.1142/S0129054100000260.
  • Frank Gurski, Egon Wanke. Graph-Theoretic Concepts in Computer Science: 26th International Workshop, WG 2000, Konstanz, Germany, June 15–17, 2000, Proceedings / Ulrik Brandes, Dorothea Wagner. — Berlin: Springer, 2000. — Т. 1928. — С. 196–205. — (Lecture Notes in Computer Science). — doi:10.1007/3-540-40064-8_19.
  • Frank Gurski, Egon Wanke. Line graphs of bounded clique-width // Discrete Mathematics. — 2007. — Т. 307, вып. 22. — С. 2734–2754. — doi:10.1016/j.disc.2007.01.020.
  • Frank Gurski, Egon Wanke. The NLC-width and clique-width for powers of graphs of bounded tree-width // Discrete Applied Mathematics. — 2009. — Т. 157, вып. 4. — С. 583–595. — doi:10.1016/j.dam.2008.08.031.
  • Petr Hliněný, Sang-il Oum. Finding branch-decompositions and rank-decompositions // SIAM Journal on Computing. — 2008. — Т. 38, вып. 3. — С. 1012–1032. — doi:10.1137/070685920.
  • Sang-il Oum, Paul Seymour. Approximating clique-width and branch-width // Journal of Combinatorial Theory. — 2006. — Т. 96, вып. 4. — С. 514–528. — doi:10.1016/j.jctb.2005.10.006.
  • Sang-il Oum. Approximating rank-width and clique-width quickly // ACM Transactions on Algorithms. — 2009. — Т. 5, вып. 1. — С. Art. 10, 20. — doi:10.1007/11604686_5.
  • Ioan Todinca. Graph-theoretic concepts in computer science. — Springer, Berlin, 2003. — Т. 2880. — С. 370–382. — (Lecture Notes in Comput. Sci.). — doi:10.1007/978-3-540-39890-5_32.
  • Egon Wanke. k-NLC graphs and polynomial algorithms // Discrete Applied Mathematics. — 1994. — Т. 54, вып. 2—3. — С. 251–266. — doi:10.1016/0166-218X(94)90026-4.
Источник — https://ru.wikipedia.org/w/index.php?title=Кликовая_ширина&oldid=133518368