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

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

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

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

| ∃R,G,B. | (∀v∈V. (v∈R ∨ v∈G ∨ v∈B)) ∧

| (∀u,v∈V. ((u∈R ∧ v∈R) ∨ (u∈G ∧ v∈G) ∨ (u∈B ∧ v∈B)) → ¬adj(u,v)).

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

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

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

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

Модульная сравнимость Другое направление расширения теоремы Курселя касается логических формул, включающих предикаты для подсчёта длины теста. В этом контексте невозможно осуществить произвольные арифметические операции над размерами множеств, и даже невозможно проверить, что множества имеют один и тот же размер. Однако MSO1 и MSO2 могут быть расширены до логик, называемых CMSO1 и CMSO2, которые включают для любых двух констант q и r предикат , который проверяет, сравнима ли мощность множества 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-многообразий, а также как решить эффективно некоторые задачи в , когда многообразие имеет триангуляцию (исключая вырожденные симплексы), двойственный граф которой имеет малую древовидную ширину.

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

Примечания

Литература

Категория:Алгоритмы на графах Категория:Теория миноров графов Курселя