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

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

  1. Создание новой вершины v с меткой i (отмечено i (v) )
  2. Непересекающееся объединение двух помеченных графов G и H (обозначено )
  3. Соединяя ребром каждую вершину с меткой i с каждой вершиной с меткой j (обозначаемой η (i, j) ), где
  4. Переименование метки i в метку j (обозначается ρ ( i , j ))

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

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

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

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

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

Границы [ править ]

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

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

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

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

Нерешенная задача по математике :

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

(больше нерешенных задач по математике)

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

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

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

Отношение к ширине дерева [ править ]

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

Заметки [ править ]

  1. ^ Courcelle, Engelfriet и Розенберг (1993) .
  2. ^ Курсель (1993) .
  3. ^ Курсель и Олариу (2000) .
  4. ^ Golumbic & Rotics (2000) .
  5. ^ Brandstädt & Lozin (2003) .
  6. ^ Brandstädt et al. (2005) ; Brandstädt et al. (2006) .
  7. ^ Brandstädt & Hundt (2008) ; Гурски и Ванке (2009) .
  8. ^ Courcelle & Olariu (2000) , следствие 3.3.
  9. ^ Курсель и Олариу (2000) , теорема 4.1.
  10. ^ Corneil & Rotics (2005) , усиление Courcelle & Olariu (2000) , теорема 5.5.
  11. ^ a b Гурски и Ванке (2000) .
  12. ^ Oum & Seymour (2006) .
  13. ^ Todinca (2003) .
  14. ^ Гурский и Ванке (2009) .
  15. ^ Cogis & Thierry (2005) .
  16. ^ a b Courcelle, Makowsky & Rotics (2000) .
  17. ^ Фомин и др. (2010) .
  18. ↑ Дворжак и Краль (2012) .
  19. ^ Corneil et al. (2012) .
  20. ^ a b Fellows et al. (2009) .
  21. ^ Oum & Seymour (2006) ; Глинены и Оум (2008) ; Оум (2009) .
  22. ^ Гурский и Ванке (2007) .

Ссылки [ править ]

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