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

В теорії графів клікова ширина графу  — це параметр, який описує структурну складність графу. Параметр тісно пов'язаний з деревною шириною, але, на відміну від деревної ширини, клікова ширина може бути обмеженою навіть для щільних графів. Клікова ширина визначається як мінімальна кількість міток, необхідних для побудови за допомогою таких 4 операцій:

  1. Створення нової вершини v з міткою i (операція i(v))
  2. Незв'язне об'єднання двох розмічених графів G і H (операція )
  3. З'єднання ребром кожної вершини з міткою i з кожною вершиною з міткою j (операція η(i, j)), де
  4. Перейменування мітки i на j (операція ρ(i,j))
Побудова дистанційно-успадковуваного графу клікової ширини 3 незв'язним об'єднанням, перейменуванням вершин і об'єднанням міток. Мітки вершин показано кольорами.

До графів з обмеженою кліковою шириною належать кографи і дистанційно-успадковувані графи. Хоча обчислення клікової ширини є 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].

Див. також

Примітки

Література

  • Andreas Brandstädt, F.F. Dragan, H.-O. Le, R. Mosca. New graph classes of bounded clique-width // Theory of Computing Systems.  2005. Т. 38 (27 лютого). С. 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 (27 лютого). С. 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 (27 лютого). С. 273–281.
  • J. Chlebíková. On the tree-width of a graph // Acta Mathematica Universitatis Comenianae.  1992. Т. 61, вип. 2 (27 лютого). С. 225–236. — (New Series).
  • O. Cogis, E. Thierry. Computing maximum stable sets for distance-hereditary graphs // Discrete Optimization.  2005. Т. 2, вип. 2 (27 лютого). С. 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 (27 лютого). С. 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 (27 лютого). С. 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 (27 лютого). С. 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 (27 лютого). С. 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 (27 лютого). С. 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 (27 лютого). С. 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 (27 лютого). С. 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 (27 лютого). С. 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 (27 лютого). С. 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 (27 лютого). С. 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 (27 лютого). С. 1012–1032. DOI:10.1137/070685920.
  • Sang-il Oum, Paul Seymour. Approximating clique-width and branch-width // Journal of Combinatorial Theory.  2006. Т. 96, вип. 4 (27 лютого). С. 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 (27 лютого). С. 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 (27 лютого). С. 251–266. DOI:10.1016/0166-218X(94)90026-4.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.