Ширина клики - Clique-width

Строительство дистанционно-наследственный граф ширины клики 3 непересекающимися союзами, перемарками и соединениями ярлыков. Метки вершин показаны цветами.

В теория графов, то ширина клики из график ${displaystyle G}$ - параметр, описывающий структурную сложность графа; это тесно связано с ширина дерева, но в отличие от ширины дерева она может быть ограничена даже при плотные графы.Он определяется как минимальное количество меток, необходимых для построения ${displaystyle G}$ с помощью следующих 4 операций:

1. Создание новой вершины v с этикеткой я ( отметил я (v) )
2. Непересекающееся объединение двух помеченных графов грамм и ЧАС (обозначено ${displaystyle Goplus H}$ )
3. Соединяя ребром каждую вершину с меткой я в каждую вершину, помеченную j (обозначен η (i, j)), куда ${displaystyle ieq j}$
4. Переименование ярлыка я маркировать j (обозначено ρ(я,j) )

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

Последовательности построения, лежащие в основе концепции ширины клики, были сформулированы Курсель, Энгельфриет и Розенберг в 1990 г.^[1] и по Ванке (1994). Название «ширина клики» использовалось для другой концепции Хлебикова (1992). К 1993 году этот термин уже имел свое нынешнее значение.^[2]

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

Кографы - это в точности графы с шириной клики не более 2.^[3] Каждый дистанционно-наследственный граф имеет ширину клики не более 3. Однако ширина клики графов с единичными интервалами не ограничена (в зависимости от их сеточной структуры).^[4] Точно так же ширина клики двудольных графов перестановок не ограничена (на основе аналогичной структуры сетки).^[5] На основе характеристики кографов как графов без индуцированного подграфа, изоморфного бесхордовому пути с четырьмя вершинами, была классифицирована ширина клики многих классов графов, определенных запрещенными индуцированными подграфами.^[6]

Другие графы с ограниченной шириной клики включают k-листовые полномочия для ограниченных значений k; эти индуцированные подграфы из листьев дерева Т в мощность графика Т^k. Однако листовые степени с неограниченными показателями не имеют ограниченной ширины клики.^[7]

Границы

Курсель и Олариу (2000) и Корнейл и Ротикс (2005) доказали следующие оценки ширины клики некоторых графов:

• Если граф имеет ширину клики не более k, то и каждый индуцированный подграф графа.^[8]
• В дополнительный граф графа ширины клики k имеет ширину клики не более 2k.^[9]
• Графики ширина дерева ш иметь ширину клики не более 3 · 2^{ш − 1}. Экспоненциальная зависимость в этой оценке необходима: существуют графы, ширина клики которых экспоненциально больше ширины их дерева.^[10] С другой стороны, графы ограниченной ширины клики могут иметь неограниченную ширину дерева; например, п-вертекс полные графики имеют ширину клики 2, но ширину дерева п − 1. Однако графы ширины клики k у которых нет полный двудольный граф K_т,т как подграф имеют ширину не более 3k(т − 1) − 1. Поэтому для каждой семьи разреженные графики, ограниченная ширина дерева эквивалентна ограниченной ширине клики.^[11]
• Другой параметр графика, ширина ранга, ограничена в обоих направлениях шириной клики: rank-width ≤ clique-width ≤ 2^{ширина ранга + 1}.^[12]

Кроме того, если график грамм имеет ширину клики k, то мощность графика грамм^c имеет ширину клики не более 2kc^k.^[13] Хотя существует экспоненциальный пробел как в оценке ширины клики по ширине дерева, так и в оценке ширины клики для степеней графа, эти границы не дополняют друг друга: если граф грамм имеет ширину дерева ш, тогда грамм^c имеет ширину клики не более 2(c + 1)^{ш + 1} − 2, только однократно экспоненциальный по ширине дерева.^[14]

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

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

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

Также можно найти оптимальные раскраски графиков или же Гамильтоновы циклы для графов с ограниченной шириной клики за полиномиальное время, когда последовательность построения известна, но показатель полинома увеличивается с увеличением ширины клики, и данные теории вычислительной сложности показывают, что эта зависимость, вероятно, необходима.^[17]Графы ограниченной ширины клики имеют вид χ-ограниченный, что означает, что их хроматическое число не более чем функция размера их самой большой группы.^[18]

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

Отношение к ширине дерева

Теория графов ограниченной ширины клики похожа на теорию графов ограниченной ширины. ширина дерева, но в отличие от Treewidth позволяет плотные графы. Если семейство графов имеет ограниченную ширину клики, то либо оно имеет ограниченную ширину дерева, либо каждую полный двудольный граф является подграфом графа в семье.^[11] Ширина дерева и ширина клики также связаны через теорию линейные графики: семейство графов имеет ограниченную ширину дерева тогда и только тогда, когда их линейные графы имеют ограниченную ширину клики.^[22]

Примечания

1. Курсель, Энгельфриет и Розенберг (1993).
2. Курсель (1993).
3. Курсель и Олариу (2000).
4. Голумбик и Ротикс (2000).
5. Брандштедт и Лозин (2003).
6. Brandstädt et al. (2005); Brandstädt et al. (2006).
7. Brandstädt & Hundt (2008); Гурски и Ванке (2009).
8. Курсель и Олариу (2000), Следствие 3.3.
9. Курсель и Олариу (2000), Теорема 4.1.
10. Корнейл и Ротикс (2005), укрепление Курсель и Олариу (2000), Теорема 5.5.
11. Гурски и Ванке (2000).
12. Оум и Сеймур (2006).
13. Тодинка (2003).
14. Гурски и Ванке (2009).
15. Cogis & Thierry (2005).
16. Курсель, Маковски и Ротикс (2000).
17. Фомин и др. (2010).
18. Дворжак и Краль (2012).
19. Corneil et al. (2012).
20. Fellows et al. (2009).
21. Оум и Сеймур (2006); Глинены и Оум (2008); Оум (2009).
22. Гурски и Ванке (2007).

Рекомендации

• Брандштадт, А.; Dragan, F.F .; Le, H.-O .; Моска, Р. (2005), "Новые классы графов ограниченной ширины клики", Теория вычислительных систем, 38 (5): 623–645, CiteSeerX  10.1.1.3.5994, Дои:10.1007 / s00224-004-1154-6, S2CID  2309695.
• Брандштадт, А.; Engelfriet, J .; Le, H.-O .; Лозин, В.В. (2006), "Ширина клики для запрещенных подграфов с 4 вершинами", Теория вычислительных систем, 39 (4): 561–590, Дои:10.1007 / s00224-005-1199-1, S2CID  20050455.
• Брандштадт, Андреас; Хундт, Кристиан (2008), «Птолемеевы графы и интервальные графы являются листовыми степенями», ЛАТИН 2008: Теоретическая информатика., Конспект лекций по вычисл. Наук, 4957, Springer, Berlin, pp. 479–491, Дои:10.1007/978-3-540-78773-0_42, МИСТЕР  2472761.
• Брандштадт, А.; Лозин, В.В. (2003), "О линейной структуре и ширине клики двудольных графов перестановок", Ars Combinatoria, 67: 273–281, CiteSeerX  10.1.1.16.2000.
• Хлебикова, J. ​​(1992), "О древовидной ширине графа", Acta Mathematica Universitatis Comenianae, Новая серия, 61 (2): 225–236, CiteSeerX  10.1.1.30.3900, МИСТЕР  1205875.
• Cogis, O .; Тьерри, Э. (2005), "Вычисление максимально стабильных множеств для дистанционно-наследственных графов", Дискретная оптимизация, 2 (2): 185–188, Дои:10.1016 / j.disopt.2005.03.004, МИСТЕР  2155518.
• Корнейл, Дерек Г.; Хабиб, Мишель; Ланлиньель, Жан-Марк; Рид, Брюс; Rotics, Udi (2012), "Распознавание клики шириной за полиномиальное время. ≤ 3 графики », Дискретная прикладная математика, 160 (6): 834–865, Дои:10.1016 / j.dam.2011.03.020, МИСТЕР  2901093.
• Корнейл, Дерек Г.; Ротикс, Уди (2005), "О взаимосвязи между шириной клики и шириной дерева", SIAM Журнал по вычислениям, 34 (4): 825–847, Дои:10.1137 / S0097539701385351, МИСТЕР  2148860.
• Курсель, Бруно; Engelfriet, Joost; Розенберг, Гжегож (1993), "Ручная перезапись грамматик гиперграфов", Журнал компьютерных и системных наук, 46 (2): 218–270, Дои:10.1016 / 0022-0000 (93) 90004-Г, МИСТЕР  1217156. Представлено в предварительной форме в Graph grammars and their application to computer science (Bremen, 1990), МИСТЕР1431281.
• Курсель, Б. (1993), "Монадическая логика второго порядка и ориентация гиперграфа", Материалы восьмого ежегодного симпозиума IEEE по логике в компьютерных науках (LICS '93), стр. 179–190, Дои:10.1109 / LICS.1993.287589, S2CID  39254668.
• Курсель, Б.; Маковский, Дж.; Ротикс, У. (2000), "Линейно решаемые задачи оптимизации по времени на графах с ограниченной шириной клики", Теория вычислительных систем, 33 (2): 125–150, CiteSeerX  10.1.1.414.1845, Дои:10.1007 / s002249910009, S2CID  15402031.
• Курсель, Б.; Олариу, С. (2000), «Верхние границы ширины клики графов», Дискретная прикладная математика, 101 (1–3): 77–144, Дои:10.1016 / S0166-218X (99) 00184-5.
• Дворжак, Зденек; Краль, Даниэль (2012), "Классы графов с разложениями малого ранга χ-ограничены", Электронный журнал комбинаторики, 33 (4): 679–683, arXiv:1107.2161, Дои:10.1016 / j.ejc.2011.12.005, S2CID  5530520
• Товарищи, Майкл Р.; Розамонд, Фрэнсис А.; Ротикс, Уди; Зейдер, Стефан (2009), «Ширина клики NP-полная», Журнал SIAM по дискретной математике, 23 (2): 909–939, Дои:10.1137/070687256, МИСТЕР  2519936.
• Фомин, Федор В .; Головач, Петр А .; Локштанов Даниил; Саураб, Сакет (2010), "Непреодолимость параметризации ширины клики", SIAM Журнал по вычислениям, 39 (5): 1941–1956, CiteSeerX  10.1.1.220.1712, Дои:10.1137/080742270, МИСТЕР  2592039.
• Голумбик, Мартин Чарльз; Ротикс, Уди (2000), "О ширине клики некоторых классов совершенных графов", Международный журнал основ информатики, 11 (3): 423–443, Дои:10.1142 / S0129054100000260, МИСТЕР  1792124.
• Гурски, Франк; Ванке, Эгон (2000), "Древовидность ограниченных графов шириной клики без K_{п, п}", в Брандесе, Ульрик; Вагнер, Доротея (ред.), Теоретико-графические концепции в компьютерных науках: 26-й международный семинар, WG 2000, Констанц, Германия, 15–17 июня 2000 г., Труды, Конспект лекций по информатике, 1928, Берлин: Springer, стр. 196–205, Дои:10.1007/3-540-40064-8_19, МИСТЕР  1850348.
• Гурски, Франк; Ванке, Эгон (2007), "Линейные графы ограниченной ширины клики", Дискретная математика, 307 (22): 2734–2754, Дои:10.1016 / j.disc.2007.01.020.
• Гурски, Франк; Ванке, Эгон (2009), "Ширина NLC и ширина клики для степеней графов ограниченной древовидной ширины", Дискретная прикладная математика, 157 (4): 583–595, Дои:10.1016 / j.dam.2008.08.031, МИСТЕР  2499471.
• Глинены, Петр; Оум, Санг-ил (2008), «Нахождение разложений по ветвям и разложения по рангам», SIAM Журнал по вычислениям, 38 (3): 1012–1032, CiteSeerX  10.1.1.94.2272, Дои:10.1137/070685920, МИСТЕР  2421076.
• Оум, Санг-ил; Сеймур, Пол (2006), «Приближение ширины клики и ширины ветвления», Журнал комбинаторной теории, Серия B, 96 (4): 514–528, Дои:10.1016 / j.jctb.2005.10.006, МИСТЕР  2232389.
• Оум, Санг-ил (2009), «Быстрое приближение ширины ранга и ширины клики», ACM-транзакции на алгоритмах, Конспект лекций по информатике, 5 (1): Ст. 10, 20, CiteSeerX  10.1.1.574.8156, Дои:10.1007/11604686_5, ISBN  978-3-540-31000-6, МИСТЕР  2479181.
• Тодинка, Иоан (2003), "Раскрашивающие способности графов ограниченной ширины клики", Теоретико-графические концепции в информатике, Конспект лекций по вычисл. Наук, 2880, Springer, Berlin, pp. 370–382, Дои:10.1007/978-3-540-39890-5_32, МИСТЕР  2080095.
• Ванке, Эгон (1994) "k-NLC графики и полиномиальные алгоритмы », Дискретная прикладная математика, 54 (2–3): 251–266, Дои:10.1016 / 0166-218X (94) 90026-4, МИСТЕР  1300250.