Теорема Курселя

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

Составы

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

В одном варианте логики монадического графа второго порядка, известном как MSO ₁ , граф описывается набором вершин и бинарным отношением смежности. $\operatorname {adj} (.,.)$, а ограничение на монадическую логику означает, что рассматриваемое свойство графа может быть определено в терминах наборов вершин данного графа, но не в терминах наборов ребер или наборов кортежей вершин.

Например, свойство графа раскрашиваться в три цвета (представленных тремя наборами вершин $R$, $G$, и $B$) может быть определен монадической формулой второго порядка $${\begin{aligned}\exists R\ \exists G\ \exists B\ {\Bigl (}&\forall v\ (v\in R\vee v\in G\vee v\in B)\wedge {}\\&\forall u\ \forall v\ {\bigl (}(u\in R\wedge v\in R)\rightarrow \lnot \operatorname {adj} (u,v){\bigr )}\wedge {}\\&\forall u\ \forall v\ {\bigl (}(u\in G\wedge v\in G)\rightarrow \lnot \operatorname {adj} (u,v){\bigr )}\wedge {}\\&\forall u\ \forall v\ {\bigl (}(u\in B\wedge v\in B)\rightarrow \lnot \operatorname {adj} (u,v){\bigr )}{\Bigr )}\end{aligned}}$$ с соглашением об именах, согласно которому переменные в верхнем регистре обозначают наборы вершин, а переменные в нижнем регистре обозначают отдельные вершины (так что явное объявление того, что можно опустить из формулы). Первая часть этой формулы гарантирует, что три цветовых класса охватывают все вершины графа, а остальная часть гарантирует, что каждый из них образует независимое множество . (Можно также добавить в формулу пункты, гарантирующие, что три цветовых класса не пересекаются, но это не влияет на результат.) Таким образом, по теореме Курселя, 3-раскраска графов ограниченной древовидной ширины может быть проверена в линейное время.

Для этого варианта графовой логики теорему Курселя можно расширить от ширины дерева до ширины клики : для каждого фиксированного _{MSO 1} свойства $\Pi$, и каждая фиксированная граница $b$ относительно ширины клики графа существует алгоритм с линейным временем для проверки того, имеет ли граф ширину клика не более $b$ имеет собственность $\Pi$. Первоначальная формулировка этого результата требовала, чтобы входной граф был задан вместе с конструкцией, доказывающей, что он имеет ограниченную ширину клики, но более поздние алгоритмы аппроксимации ширины клики устранили это требование.

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

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

Например, свойство наличия гамильтонова цикла может быть выражено в MSO ₂ путем описания цикла как набора ребер, включающего ровно два ребра, инцидентных каждой вершине, так что каждое непустое собственное подмножество вершин имеет ребро в предполагаемом цикле. ровно с одной конечной точкой в ​​подмножестве. Однако гамильтоновость не может быть выражена в MSO ₁ .

Маркированные графики

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

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

Другое направление развития теоремы Курселя касается логических формул, включающих предикаты для подсчета размера теста. В этом контексте невозможно выполнять произвольные арифметические операции над размерами наборов или даже проверять, имеют ли два набора одинаковый размер. Однако MSO ₁ и MSO ₂ могут быть расширены до логики, называемой CMSO ₁ и CMSO ₂ , которая включает для каждых двух констант q и r предикат $\operatorname {card} _{q,r}(S)$ который проверяет, множества S r ли конгруэнтна по модулю q мощность . Теорему Курселя можно распространить на эти логики.

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

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

Пространственная сложность

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

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

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

Более подробно, два графа G ₁ и G ₂ , каждый с заданным подмножеством T вершин, называемых терминалами, могут быть определены как эквивалентные относительно формулы MSO F, если для всех других графов H, пересечение которых с G ₁ и G ₂ состоит только из вершин из T , два графа G ₁ ∪ H и G ₂ ∪ H ведут себя одинаково по отношению к F : либо они оба моделируют F , либо они оба не моделируют F . Это отношение эквивалентности , и индукцией по длине F можно показать , что (когда размеры T и F оба ограничены) оно имеет конечное число классов эквивалентности .

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

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

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

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

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

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

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

В качестве частичного обратного, Сизе (1991) доказал, что всякий раз, когда семейство графов имеет разрешимую проблему выполнимости MSO ₂ , это семейство должно иметь ограниченную ширину дерева. Доказательство основано на теореме Робертсона и Сеймура о том, что семейства графов с неограниченной шириной дерева имеют сколь угодно большие сетки миноры . Сизи также предположил, что каждое семейство графов с разрешимой проблемой выполнимости MSO ₁ должно иметь ограниченную ширину клики; это не доказано, но ослабление гипотезы о замене MSO ₁ на CMSO ₁ верно.

Приложения

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

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

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

Методы, основанные на теореме Курселя, также применяются в теории баз данных . представление знаний и рассуждение , теория автоматов , и проверка модели .