Теорема Курселя - Courcelles theorem

При изучении график алгоритмы, Теорема Курселя утверждение, что каждый свойство графа определяемый в монадический второй порядок логика графиков можно решить в линейное время на графах ограниченных ширина дерева.[1][2][3] Результат был впервые доказан Бруно Курсель в 1990 году[4] и независимо заново открыты Бори, Паркер и Тови (1992).[5]Считается архетипом алгоритмической мета-теоремы.[6][7]

Составы

Наборы вершин

В одном из вариантов монадической графической логики второго порядка, известной как MSO1, то график описывается набором вершин V и бинарное отношение смежности adj (.,.), и ограничение на монадическую логику означает, что рассматриваемое свойство графа может быть определено в терминах наборов вершин данного графа, но не в терминах наборов ребер или множеств наборов вершин.

Например, свойство графа быть раскрашиваемый с тремя цветами (представлен тремя наборами вершин р, грамм, и B) может быть определена монадической формулой второго порядка

∃р,грамм,B.(∀v∈V. (v∈р ∨ v∈грамм ∨ v∈B)) ∧
(∀ты,v∈V. ((ты∈р ∧ v∈р) ∨ (ты∈грамм ∧ v∈грамм) ∨ (ты∈B ∧ v∈B)) → ¬adj (ты,v)).

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

Для этого варианта логики графа теорема Курселя может быть расширена от ширины дерева до ширина клики: для каждого фиксированного MSO1 свойство п, и каждая фиксированная граница б на ширине клики графа существует алгоритм линейного времени для проверки того, не превышает ли граф шириной клики б имеет собственность п.[8] Первоначальная формулировка этого результата требовала, чтобы входной граф был задан вместе с конструкцией, доказывающей, что он имеет ограниченную ширину клики, но позже аппроксимационные алгоритмы для clique-width это требование снято.[9]

Наборы кромок

Теорема Курселя также может использоваться с более сильным вариантом монадической логики второго порядка, известной как MSO.2. В этой постановке граф представлен набором V вершин, множество E ребер и отношение инцидентности между вершинами и ребрами. Этот вариант позволяет количественно оценивать наборы вершин или ребер, но не более сложные отношения на наборах вершин или ребер.

Например, свойство иметь Гамильтонов цикл может быть выражено в MSO2 описывая цикл как набор ребер, который включает в себя ровно два ребра, инцидентных каждой вершине, так что каждое непустое собственное подмножество вершин имеет ребро в предполагаемом цикле с ровно одной конечной точкой в ​​подмножестве. Однако гамильтоничность не может быть выражена в MSO.1.[10]

Помеченные графики

Можно применить те же результаты к графам, в которых вершины или ребра имеют этикетки из фиксированного конечного набора, либо путем расширения логики графа для включения предикатов, описывающих метки, либо путем представления меток неквантифицированным набором вершин или переменными набора ребер.[11]

Модульные сравнения

Другое направление расширения теоремы Курселя касается логических формул, которые включают предикаты для подсчета размера теста. В этом контексте невозможно выполнять произвольные арифметические операции с размерами множеств или даже проверять, имеют ли два множества одинаковый размер. , MSO1 и MSO2 может быть расширен до логики под названием CMSO1 и CMSO2, которые включают для каждых двух констант q и р предикат который проверяет, мощность набора S является конгруэнтный к р по модулюq. На эти логики можно распространить теорему Курселя.[4]

Решение против оптимизации

Как указано выше, теорема Курселя применима в первую очередь к проблемы решения: есть ли у графа свойство или нет. Однако те же методы также позволяют решить проблемы оптимизации в котором вершины или ребра графа имеют целочисленные веса, и ищется набор вершин с минимальным или максимальным весом, который удовлетворяет заданному свойству, выраженному в логике второго порядка. Эти задачи оптимизации могут быть решены за линейное время на графах ограниченной ширины клики.[8][11]

Космическая сложность

Вместо того, чтобы ограничивать временная сложность алгоритма, распознающего свойство MSO на графах с ограниченной шириной дерева, также можно анализировать космическая сложность такого алгоритма; то есть объем памяти, необходимый сверх размера самого ввода (который, как предполагается, будет представлен только для чтения, так что его требования к пространству не могут быть использованы для других целей). В частности, можно распознавать графы с ограниченной шириной дерева и любое свойство MSO на этих графах по детерминированная машина Тьюринга который использует только логарифмическое пространство.[12]

Стратегия доказательства и сложность

Типичный подход к доказательству теоремы Курселя включает построение конечного восходящего древовидный автомат что действует на разложение деревьев данного графа.[6]

Более подробно два графика грамм1 и грамм2, каждый с указанным подмножеством Т вершин, называемых терминалами, можно определить как эквивалентные по формуле MSO F если для всех остальных графиков ЧАС чье пересечение с грамм1 и грамм2 состоит только из вершин в Т, два графикаграмм1 ∪ ЧАС и грамм2 ∪ ЧАС вести себя так же в отношении F: либо они оба моделируют F или они оба не моделируют F. Это отношение эквивалентности, и это можно показать индукцией по длине F что (когда размеры Т и F оба ограничены) имеет конечное число классы эквивалентности.[13]

Древовидное разложение данного графа грамм состоит из дерева и для каждого узла дерева подмножество вершин грамм называется сумка. Он должен удовлетворять двум свойствам: для каждой вершины v из грамм, пакеты, содержащие v должен быть связан с непрерывным поддеревом дерева, и для каждого ребра УФ из грамм, должен быть пакет, содержащий оба ты и v.Вершины в сумке можно рассматривать как терминалы подграфа грамм, представленный поддеревом дерева декомпозиции, спускающимся из этого мешка. Когда грамм имеет ограниченную ширину дерева, имеет разложение по дереву, в котором все пакеты имеют ограниченный размер, и такое разложение может быть найдено за управляемое время с фиксированными параметрами.[14] Более того, это разложение дерева можно выбрать так, чтобы оно образовывало двоичное дерево, только с двумя дочерними поддеревьями на сумку. Следовательно, можно выполнить восходящее вычисление для этого разложения дерева, вычисляя идентификатор для класса эквивалентности поддерева, имеющего корень в каждом мешке, путем комбинирования ребер, представленных внутри мешка, с двумя идентификаторами для классов эквивалентности его двух дети.[15]

Размер сконструированного таким образом автомата не является оптимальным. элементарная функция размера входной формулы MSO. Эта неэлементарная сложность необходима в том смысле, что (если только P = NP ) невозможно протестировать свойства MSO на деревьях за время, которое можно контролировать с фиксированным параметром с элементарной зависимостью от параметра.[16]

Теорема Боянчика-Пилипчука

Доказательства теоремы Курселя показывают более сильный результат: не только каждое (считающее) монадическое свойство второго порядка может быть распознано за линейное время для графов с ограниченной шириной дерева, но также оно может быть распознано конечным состоянием. древовидный автомат. Курсель предположил обратное: если свойство графов с ограниченной шириной дерева распознается древовидным автоматом, то оно может быть определено при подсчете монадической логики второго порядка. В 1998 г. Лапуар (1998), заявил о разрешении гипотезы.[17] Однако многие считают это доказательство неудовлетворительным.[18][19] До 2016 г. было разрешено лишь несколько частных случаев: в частности, гипотеза была доказана для графов шириной не более трех,[20] для k-связных графов ширины дерева k, для графов постоянной ширины дерева и хордальности, а также для k-внешнепланарных графов. Общая версия гипотезы была окончательно доказана Миколай Боянчик и Михал Пилипчук.[21]

Более того, для Графики Халина (частный случай трех графов шириной в три) подсчет не требуется: для этих графов каждое свойство, которое может быть распознано древовидным автоматом, также может быть определено в монадической логике второго порядка. То же самое можно сказать и о некоторых классах графов, в которых разложение дерева может быть описано в MSOL. Однако это не может быть верно для всех графов с ограниченной шириной дерева, потому что в общем случае подсчет добавляет дополнительную мощность по сравнению с монадической логикой второго порядка без подсчета. Например, графы с четным числом вершин можно распознать с помощью счета, но не без него.[19]

Выполнимость и теорема Зеезе

В проблема выполнимости для формулы монадической логики второго порядка является проблема определения, существует ли хотя бы один граф (возможно, в пределах ограниченного семейства графов), для которого формула верна. Для произвольных семейств графов и произвольных формул эта проблема неразрешимый. Однако выполнимость MSO2 формула разрешима для графов ограниченной ширины дерева, и выполнимость MSO1 формулы разрешима для графов ограниченной ширины клики. Доказательство включает построение древовидного автомата для формулы и затем проверку того, есть ли у автомата приемный путь.

В качестве частичного обратного Seese (1991) доказал, что всякий раз, когда семейство графов имеет разрешимый MSO2 проблема выполнимости, семейство должно иметь ограниченную ширину дерева. Доказательство основано на теореме Робертсон и Сеймур что семейства графов с неограниченной шириной дерева имеют сколь угодно большие сетка несовершеннолетние.[22] Зее также предположил, что каждое семейство графов с разрешимым MSO1 задача выполнимости должна иметь ограниченную ширину клики; это не было доказано, но это ослабление гипотезы, заменяющей MSO1 от CMSO1 правда.[23]

Приложения

Grohe (2001) использовал теорему Курселя, чтобы показать, что вычисление номер перехода графа грамм является управляемый с фиксированными параметрами с квадратичной зависимостью от размера грамм, улучшая алгоритм кубического времени на основе Теорема Робертсона – Сеймура. Дополнительное последующее улучшение линейное время к Каварабаяши и Рид (2007) следует тому же подходу. Если данный граф грамм имеет небольшую ширину дерева, теорема Курселя может быть применена непосредственно к этой задаче. С другой стороны, если грамм имеет большую ширину дерева, тогда он содержит большой сетка незначительный, в рамках которого можно упростить график, оставив номер пересечения неизменным. Алгоритм Гроэ выполняет эти упрощения до тех пор, пока оставшийся граф не будет иметь небольшую ширину дерева, а затем применяет теорему Курселя для решения сокращенной подзадачи.[24][25]

Готтлоб и Ли (2007) заметил, что теорема Курселя применима к нескольким задачам поиска минимального многоходового порезы в графе, когда структура, образованная графом и набором пар разрезов, имеет ограниченную ширину дерева. В результате они получают управляемый алгоритм с фиксированными параметрами для этих проблем, параметризованный одним параметром, treewidth, улучшая предыдущие решения, которые объединяли несколько параметров.[26]

В вычислительной топологии Бертон и Дауни (2014) расширить теорему Курселя из MSO2 к форме монадической логики второго порядка на симплициальные комплексы ограниченной размерности, которая позволяет количественно оценивать симплексы любой фиксированной размерности. Как следствие, они показывают, как вычислить определенные квантовые инварианты из 3-коллекторы а также как решить определенные проблемы в дискретная теория Морса эффективно, когда многообразие имеет триангуляцию (избегающую вырожденных симплексов), двойственный граф имеет небольшую ширину дерева.[27]

Методы, основанные на теореме Курселя, также применялись к теория баз данных,[28] представление знаний и рассуждения,[29] теория автоматов,[30] и проверка модели.[31]

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

  1. ^ Эгер, Штеффен (2008), Регулярные языки, ширина дерева и теорема Курселя: введение, Издательство VDM, ISBN  9783639076332.
  2. ^ Курсель, Бруно; Энгельфриет, Джуст (2012), Структура графа и монадическая логика второго порядка: теоретико-языковой подход (PDF), Энциклопедия математики и ее приложений, 138, Издательство Кембриджского университета, ISBN  9781139644006, Zbl  1257.68006.
  3. ^ Дауни, Родни Г.; Товарищи, Майкл Р. (2013), «Глава 13: Теорема Курселя», Основы параметризованной сложности, Texts in Computer Science, London: Springer, pp. 265–278, CiteSeerX  10.1.1.456.2729, Дои:10.1007/978-1-4471-5559-1, ISBN  978-1-4471-5558-4, МИСТЕР  3154461, S2CID  23517218.
  4. ^ а б Курсель, Бруно (1990), "Монадическая логика графов второго порядка. I. Узнаваемые множества конечных графов", Информация и вычисления, 85 (1): 12–75, Дои:10.1016 / 0890-5401 (90) 90043-Н, МИСТЕР  1042649, Zbl  0722.03008
  5. ^ Бори, Ричард Б .; Паркер, Р. Гэри; Тови, Крейг А. (1992), "Автоматическая генерация алгоритмов линейного времени из описаний задач исчисления предикатов на рекурсивно построенных семействах графов", Алгоритмика, 7 (5–6): 555–581, Дои:10.1007 / BF01758777, МИСТЕР  1154588, S2CID  22623740.
  6. ^ а б Кнейс, Иоахим; Лангер, Александр (2009), "Практический подход к теореме Курселя", Электронные заметки по теоретической информатике, 251: 65–81, Дои:10.1016 / j.entcs.2009.08.028.
  7. ^ Лэмпис, Майкл (2010), «Алгоритмические мета-теоремы для ограничений ширины дерева», в де Берг, Марк; Мейер, Ульрих (ред.), Proc. 18-й ежегодный европейский симпозиум по алгоритмам, Конспект лекций по информатике, 6346, Springer, стр. 549–560, Дои:10.1007/978-3-642-15775-2_47, Zbl  1287.68078.
  8. ^ а б Courcelle, B .; Маковски, Дж. А .; Ротикс, У. (2000), "Линейно разрешимые задачи оптимизации по времени на графах ограниченной ширины клики", Теория вычислительных систем, 33 (2): 125–150, CiteSeerX  10.1.1.414.1845, Дои:10.1007 / s002249910009, МИСТЕР  1739644, S2CID  15402031, Zbl  1009.68102.
  9. ^ Оум, Санг-ил; Сеймур, Пол (2006), «Приближение ширины клики и ширины ветвления», Журнал комбинаторной теории, Серия B, 96 (4): 514–528, Дои:10.1016 / j.jctb.2005.10.006, МИСТЕР  2232389.
  10. ^ Курсель и Энгельфриет (2012), Предложение 5.13, с. 338.
  11. ^ а б Арнборг, Стефан; Лагергрен, Йенс; Зее, Детлеф (1991), "Простые задачи для древовидных графов", Журнал алгоритмов, 12 (2): 308–340, CiteSeerX  10.1.1.12.2544, Дои:10.1016 / 0196-6774 (91) 90006-К, МИСТЕР  1105479.
  12. ^ Эльберфельд, Майкл; Якоби, Андреас; Тантау, Тиль (октябрь 2010 г.), "Логпространственные версии теорем Бодлендера и Курселя" (PDF), Proc. 51-й ежегодный симпозиум IEEE по основам компьютерных наук (FOCS 2010), стр. 143–152, Дои:10.1109 / FOCS.2010.21, S2CID  1820251.
  13. ^ Дауни и товарищи (2013), Теорема 13.1.1, с. 266.
  14. ^ Дауни и товарищи (2013), Раздел 10.5: Теорема Бодлендера, стр. 195–203.
  15. ^ Дауни и товарищи (2013), Раздел 12.6: Древовидные автоматы, стр. 237–247.
  16. ^ Фрик, Маркус; Grohe, Мартин (2004), «Снова о сложности логики первого порядка и монадической логики второго порядка», Анналы чистой и прикладной логики, 130 (1–3): 3–31, Дои:10.1016 / j.apal.2004.01.007, МИСТЕР  2092847.
  17. ^ Лапуар, Дени (1998), "Узнаваемость равна монадической определимости второго порядка для множеств графов ограниченной древовидной ширины", STACS 98: 15-й ежегодный симпозиум по теоретическим аспектам компьютерных наук Париж, Франция, 27 февраля 1998 г., Материалы, стр. 618–628, Bibcode:1998LNCS.1373..618L, CiteSeerX  10.1.1.22.7805, Дои:10.1007 / bfb0028596.
  18. ^ Courcelle, B .; Engelfriet., J. (2012), "Структура графа и монадическая логика второго порядка - теоретико-языковой подход", Энциклопедия математики и ее приложений, 138, Издательство Кембриджского университета.
  19. ^ а б Джаффке, Ларс; Бодландер, Ханс Л. (2015), MSOL-определимость равна узнаваемости графов Халина и ограниченной степени k-апланарные графики, arXiv:1503.01604, Bibcode:2015arXiv150301604J.
  20. ^ Каллер, Д. (2000), "Определимость равна узнаваемости частичных 3-деревьев и k-связанный частичный k-деревья ", Алгоритмика, 27 (3): 348–381, Дои:10.1007 / s004530010024, S2CID  39798483.
  21. ^ Боянчик, Миколай; Пилипчук, Михал (2016), «Определимость равна узнаваемости для графов с ограниченной шириной дерева», Материалы 31-го ежегодного симпозиума ACM / IEEE по логике в компьютерных науках (LICS 2016), стр. 407–416, arXiv:1605.03045, Дои:10.1145/2933575.2934508, S2CID  1213054.
  22. ^ Сизе, Д. (1991), "Структура моделей разрешимых монадических теорий графов", Анналы чистой и прикладной логики, 53 (2): 169–195, Дои:10.1016 / 0168-0072 (91) 90054-П, МИСТЕР  1114848.
  23. ^ Курсель, Бруно; Оум, Санг-ил (2007), «Вершины-миноры, монадическая логика второго порядка и гипотеза Зее» (PDF), Журнал комбинаторной теории, Серия B, 97 (1): 91–126, Дои:10.1016 / j.jctb.2006.04.003, МИСТЕР  2278126.
  24. ^ Grohe, Мартин (2001), "Вычисление числа пересечений в квадратичном времени", Материалы тридцать третьего ежегодного симпозиума ACM по теории вычислений (STOC '01), стр. 231–236, arXiv:cs / 0009010, Дои:10.1145/380752.380805, S2CID  724544.
  25. ^ Каварабаяси, Кен-ичи; Рид, Брюс (2007), «Вычисление числа пересечений за линейное время», Материалы тридцать девятого ежегодного симпозиума ACM по теории вычислений (STOC '07), стр. 382–390, Дои:10.1145/1250790.1250848, S2CID  13000831.
  26. ^ Готтлоб, Георг; Ли, Стефани Тьен (2007), «Логический подход к проблемам с несколькими резцами», Письма об обработке информации, 103 (4): 136–141, Дои:10.1016 / j.ipl.2007.03.005, МИСТЕР  2330167.
  27. ^ Бертон, Бенджамин А .; Дауни, Родни Г. (2014), Теорема Курселя для триангуляций, arXiv:1403.2926, Bibcode:2014arXiv1403.2926B. Краткое сообщение, Международный конгресс математиков, 2014.
  28. ^ Grohe, Мартин; Мариньо, Джулиан (1999), "Определимость и описательная сложность баз данных ограниченной древовидной ширины", Теория баз данных - ICDT'99: 7-я Международная конференция Иерусалим, Израиль, 10–12 января 1999 г., Труды, Конспект лекций по информатике, 1540, стр. 70–82, CiteSeerX  10.1.1.52.2984, Дои:10.1007/3-540-49257-7_6.
  29. ^ Готтлоб, Георг; Пихлер, Рейнхард; Вэй, Фанг (январь 2010 г.), «Ограниченная ширина дерева как ключ к управляемости представления знаний и рассуждений», Искусственный интеллект, 174 (1): 105–132, Дои:10.1016 / j.artint.2009.10.003.
  30. ^ Madhusudan, P .; Парлато, Дженнаро (2011), "Ширина дерева вспомогательного хранилища", Материалы 38-го ежегодного симпозиума ACM SIGPLAN-SIGACT по принципам языков программирования (POPL '11) (PDF), Уведомления SIGPLAN, 46, стр. 283–294, Дои:10.1145/1926385.1926419, S2CID  6976816
  31. ^ Обдржалек, Ян (2003), «Быстрая проверка модели мю-исчисления, когда ширина дерева ограничена», Компьютерная проверка: 15-я Международная конференция, CAV 2003, Боулдер, Колорадо, США, 8–12 июля 2003 г., Труды, Конспект лекций по информатике, 2725, стр. 80–92, CiteSeerX  10.1.1.2.4843, Дои:10.1007/978-3-540-45069-6_7.