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

Побудова дистанційно-успадковуваного графа клікової ширини 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-степені листків[en] для обмежених значень 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 (одномісна логіка другого порядку[en], вид логіки другого порядку, що дозволяє квантори над множинами вершин) має алгоритм лінійного часу для графів з обмеженою шириною за одним із формулювань теореми Курселя[20]. Можна також знайти оптимальні розмальовки або гамільтонові цикли графів з обмеженою кліковою шириною за поліноміальний час, якщо послідовність побудови графа відома, але степінь полінома збільшується зі збільшенням клікової ширини, і доводи з теорії обчислювальної складності показують, що така залежність, схоже, неминуча[21].

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

Зв'язок з деревною шириною

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

Див. також

Примітки

  1. ↑ Courcelle, Engelfriet, Rozenberg, 1993.
  2. ↑ Wanke, 1994.
  3. ↑ Chlebíková, 1992.
  4. ↑ Courcelle, 1993.
  5. ↑ а б 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. ↑ а б 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. ↑ а б Gurski, Wanke, 2000.
  17. ↑ а б Oum, Seymour, 2006.
  18. ↑ Todinca, 2003.
  19. ↑ Cogis, Thierry, 2005.
  20. ↑ а б Courcelle, Makowsky, Rotics, 2000.
  21. ↑ Fomin, Golovach, Lokshtanov, Saurabh, 2010.
  22. ↑ Corneil at al, 2012.
  23. ↑ а б 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 (25 грудня). — С. 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 (25 грудня). — С. 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 (25 грудня). — С. 273–281.
  • J. Chlebíková. On the tree-width of a graph // Acta Mathematica Universitatis Comenianae. — 1992. — Т. 61, вип. 2 (25 грудня). — С. 225–236. — (New Series).
  • O. Cogis, E. Thierry. Computing maximum stable sets for distance-hereditary graphs // Discrete Optimization. — 2005. — Т. 2, вип. 2 (25 грудня). — С. 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 (25 грудня). — С. 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 (25 грудня). — С. 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 (25 грудня). — С. 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 (25 грудня). — С. 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 (25 грудня). — С. 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 (25 грудня). — С. 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 (25 грудня). — С. 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 (25 грудня). — С. 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 (25 грудня). — С. 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 (25 грудня). — С. 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 (25 грудня). — С. 1012–1032. — DOI:10.1137/070685920.
  • Sang-il Oum, Paul Seymour. Approximating clique-width and branch-width // Journal of Combinatorial Theory. — 2006. — Т. 96, вип. 4 (25 грудня). — С. 514–528. — (Series B). — 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 (25 грудня). — С. 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 (25 грудня). — С. 251–266. — DOI:10.1016/0166-218X(94)90026-4.