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

25.09.2021

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

Формулировки

Множества вершин

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

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

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

Для этого варианта логики графов теорема Курселя может быть расширена от древесной ширины до кликовой ширины — для любого фиксированного MSO1 свойства P и любой фиксированной границы b на кликовую ширину графа существует алгоритм линейного времени проверки, имеет ли граф с кликовой шириной, не превосходящей b, свойство P.

Множества рёбер

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

Например, свойство иметь гамильтонов цикл может быть выражено в MSO2 при определении цикла как множества рёбер, включающего ровно по два ребра, инцидентных каждой вершине, такого, что любое непустое собственное подмножество вершин имеет ребро в цикле и это ребро имеет в точности одну конечную точку в подмножестве. Гамильтоновость, однако, нельзя выразить в терминах MSO1.

Модульная сравнимость

Другое направление расширения теоремы Курселя касается логических формул, включающих предикаты для подсчёта длины теста. В этом контексте невозможно осуществить произвольные арифметические операции над размерами множеств, и даже невозможно проверить, что множества имеют один и тот же размер. Однако MSO1 и MSO2 могут быть расширены до логик, называемых CMSO1 и CMSO2, которые включают для любых двух констант q и r предикат card q , r ⁡ ( S ) {displaystyle operatorname {card} _{q,r}(S)} , который проверяет, сравнима ли мощность множества S с r по модулю q. Теорему Курселя можно расширить на эти логики.

Разрешимость и оптимизация

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

Ёмкостная сложность

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

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

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

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

Древесная декомпозиция заданного графа G состоит из дерева и, для каждого узла дерева, подмножества вершин графа G, называемого корзиной. Это подмножество должно удовлетворять двум свойствам — для каждой вершины v из G корзина, содержащая v, должна быть ассоциирована с неразрывным поддеревом и для каждого ребра uv из G должна существовать корзина, содержащая как u, так и v. Вершины в корзине могут пониматься как конечные элементы подграфа G, представленные поддеревьями древесной декомпозиции, растущими из этой корзины. Если граф G имеет ограниченную древесную ширину, он имеет древесную декомпозицию, в которой все корзины имеют ограниченный размер и такое разложение может быть найдено за фиксированно-параметрически разрешимое время. Более того, можно выбрать древесное разложение, образующее двоичное дерево с только двумя дочерними поддеревьями на корзину. Таким образом, можно осуществить восходящее вычисление на этой древесной декомпозиции, вычисляя идентификатор для класса эквивалентности поддерева, имеющего корень в каждой корзине, путём комбинирования рёбер, представленных внутри корзины, с двумя идентификаторами классов эквивалентности двух дочерних элементов.

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

Гипотеза Курселя

Доказательство теоремы Курселя показывает более строгий результат — не только любое (с предикатом подсчёта длины) свойство логики второго порядка может быть распознано за линейное время для графов с ограниченной древесной шириной, но и оно может быть распознано конечным автоматом над деревом. Гипотеза Курселя обратна этому — если свойство графов с ограниченной шириной распознаётся автоматом над деревьями, то оно может быть определено в терминах логики второго порядка. Несмотря на попытки доказательства, предпринятые Лапуаром, гипотеза считается недоказанной. Однако известны некоторые специальные случаи, в частности, гипотеза верна для графов с древесной шириной три и менее.

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

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

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

В качестве частично обратного утверждения Сииз доказал, что всякий раз, когда семейство графов имеет разрешимую проблему MSO2 выполнимости, семейство должно иметь ограниченную древесную ширину. Доказательство опирается на теорему Робертсона и Сеймура о том, что семейства графов с неограниченной древесной шириной имеют произвольно большие миноры-решётки. Сииз также высказал предположение, что любое семейство графов с разрешимой проблемой MSO1 выполнимости должно иметь ограниченную кликовую ширину. Гипотеза не доказана, но ослабленная гипотеза с заменой MSO1 на CMSO1 верна.

Приложения

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

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

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

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



Имя:*
E-Mail:
Комментарий: