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

В теорії графів клікова ширина графа ${\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 і Ванке. Назву «клікова ширина» використала для іншої концепції Хлєбікова. Від 1993 термін став уживатися в сучасному значенні.

Особливі класи графів

Кографи — це точно графи з кліковою шириною, що не перевищує двох. Будь-який дистанційно-успадковуваний граф має клікову ширину, що не перевищує 3. Однак клікова ширина інтервальних графів не обмежена (згідно зі структурою ґратки). Так само не обмежена клікова ширина двочасткових графів перестановок (згідно з подібною структурою ґратки). Ґрунтуючись на описі кографів як графів без породжених підграфів, ізоморфних шляхам без хорд, класифіковано клікову ширину багатьох класів графів, визначених забороненими породженими підграфами.

Інші графи з обмеженою кліковою шириною — k-^[en] для обмежених значень k, тобто породжені підграфи листків дерева T у степені графа T^k. Однак степінь листків за необмеженого показника степеня не має обмеженої ширини листків.

Межі

Курсель і Олару, а також Корнейл і Ротікс, дали такі межі клікової ширини деяких графів:

• Якщо граф має клікову ширину максимум k, то те саме істинне для будь-якого породженого підграфа графа.
• Доповнення графа з кліковою шириною k має клікову ширину, що не перевищує 2k.
• Графи з деревною шириною w мають клікову ширину, що не перевищує 3 · 2^{w − 1}. Експоненційна залежність у межі необхідна — існують графи, клікова ширина яких експоненційно більша від їхньої деревної ширини. З іншого боку, графи з обмеженою кліковою шириною можуть мати необмежену деревну ширину. Наприклад, повні графи з n вершинами мають клікову ширину 2, але деревну ширину n − 1. Однак, графи з кліковою шириною k, які не містять повного двочасткового графа K_t,t як підграфа, мають деревну ширину, що не перевищує 3k(t − 1) − 1. Таким чином, для будь-якого сімейства розріджених графів наявність обмеження деревної ширини еквівалентне наявності обмеження клікової ширини.
• Інший параметр графів, рангова ширина, обмежена в обох напрямках кліковою шириною: рангова ширина ≤ клікової ширини ≤ 2^{рангової ширини + 1} .

Крім того, якщо граф G має клікову ширину k, то степінь графа G^c має клікову ширину, що не перевищує 2kc^k. Хоча в нерівностях для клікової ширини в порівняннях з деревною шириною та степенем графа присутня експонента, ці межі не дають суперпозиції — якщо граф G має деревну ширину w, то G^c має клікову ширину, що не перевершує 2(c + 1)^{w + 1} − 2, лише проста експонента від деревної ширини.

Обчислювальна складність

Нерозв'язана проблема математики: Чи можна граф з обмеженою кліковою шириною розпізнати за поліноміальний час? (більше нерозв'язаних проблем математики)

Багато задачі оптимізації, NP-складні для більш загальних класів графів, можна ефективно розв'язати за допомогою динамічного програмування на графах з обмеженою кліковою шириною, якщо послідовність побудови цих графів відома. Зокрема, будь-який інваріант графа, який можна виразити в MSO₁ (^[en], вид логіки другого порядку, що дозволяє квантори над множинами вершин) має алгоритм лінійного часу для графів з обмеженою шириною за одним із формулювань теореми Курселя. Можна також знайти оптимальні розмальовки або гамільтонові цикли графів з обмеженою кліковою шириною за поліноміальний час, якщо послідовність побудови графа відома, але степінь полінома збільшується зі збільшенням клікової ширини, і доводи з теорії обчислювальної складності показують, що така залежність, схоже, неминуча.

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

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

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

Див. також

• Деревна ширина
• Шляхова ширина графа

Примітки

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 (17 червня). — С. 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 (17 червня). — С. 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 // . — 2003. — Т. 67 (17 червня). — С. 273–281.
• J. Chlebíková. On the tree-width of a graph // Acta Mathematica Universitatis Comenianae. — 1992. — Т. 61, вип. 2 (17 червня). — С. 225–236. — (New Series).
• O. Cogis, E. Thierry. Computing maximum stable sets for distance-hereditary graphs // Discrete Optimization. — 2005. — Т. 2, вип. 2 (17 червня). — С. 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 // . — 2012. — Т. 160, вип. 6 (17 червня). — С. 834–865. — DOI:10.1016/j.dam.2011.03.020..
• Derek G. Corneil, Udi Rotics. On the relationship between clique-width and treewidth // . — 2005. — Т. 34, вип. 4 (17 червня). — С. 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 (17 червня). — С. 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 (17 червня). — С. 125–150. — DOI:10.1007/s002249910009.
• B. Courcelle, S. Olariu. Upper bounds to the clique width of graphs // . — 2000. — Т. 101, вип. 1–3 (17 червня). — С. 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 (17 червня). — С. 909–939. — DOI:10.1137/070687256.
• Fedor V. Fomin, Petr A. Golovach, Daniel Lokshtanov, Saket Saurabh. Intractability of clique-width parameterizations // . — 2010. — Т. 39, вип. 5 (17 червня). — С. 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 (17 червня). — С. 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 // . — 2007. — Т. 307, вип. 22 (17 червня). — С. 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 // . — 2009. — Т. 157, вип. 4 (17 червня). — С. 583–595. — DOI:10.1016/j.dam.2008.08.031.
• Petr Hliněný, Sang-il Oum. Finding branch-decompositions and rank-decompositions // . — 2008. — Т. 38, вип. 3 (17 червня). — С. 1012–1032. — DOI:10.1137/070685920.
• Sang-il Oum, . Approximating clique-width and branch-width // . — 2006. — Т. 96, вип. 4 (17 червня). — С. 514–528. — (Series B). — DOI:10.1016/j.jctb.2005.10.006.
• Sang-il Oum. Approximating rank-width and clique-width quickly // . — 2009. — Т. 5, вип. 1 (17 червня). — С. 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 // . — 1994. — Т. 54, вип. 2—3 (17 червня). — С. 251–266. — DOI:10.1016/0166-218X(94)90026-4.