Что отличает простые глобальные задачи от сложных глобальных задач на графах ограниченной длины деревьев?

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

Интересно, что даже проблемы (такие как гамильтонова траектория) глобальной природы все еще могут быть эффективно решены для ограниченных графов ширины. Для таких задач обычные алгоритмы динамического программирования должны отслеживать все способы, которыми решение может пройти через соответствующий разделитель разложения дерева (см., Например, [1]). Рандомизированные алгоритмы (основанные на так называемом cut'n'count) были приведены в [1], а улучшенные (даже детерминированные) алгоритмы были разработаны в [2].

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

Например, можно рассмотреть следующие проблемы:

Край precoloring расширение для графа с некоторыми краями цветных, решить , если эта окраска может быть расширена до надлежащего к -Станкам-раскраска графа G .$G$$k$$G$

Расширение краевой предварительной окраски (и его вариант окраски краев списков) является NP-полным для двудольных графов с параллельными сериями [3] (такие графы имеют ширину не более 2).

Раскраска ребер с минимальной суммой. Для графа найдем раскраску ребер χ : E → N, такую, что если e 1 и e 2 имеют общую вершину, то χ ( e 1 ) ≠ χ ( e 2 ) , Цель состоит в том, чтобы минимизировать E ′ χ ( E ) = ∑ e ∈ E χ ( e ) , сумму раскраски.$G=(V,E)$$\chi : E \to \mathbb{N}$$e_1$$e_2$$\chi(e_1) \neq \chi(e_2)$$E'_\chi(E) = \sum_{e \in E} \chi(e)$

Другими словами, мы должны назначить положительные целые числа ребрам графа так, чтобы смежные ребра получали разные целые числа, а сумма назначенных чисел была минимальной. Эта проблема является NP-трудной для частичных 2-деревьев [4] (т. Е. Графики ширины деревьев не более 2).

Другие такие сложные проблемы включают в себя проблему реберно-непересекающихся путей, проблему изоморфизма подграфа и проблему ширины полосы (см., Например, [5] и ссылки там). Для проблем, которые остаются трудными даже на деревьях, см. Этот вопрос .

[1] Сиган, М., Недерлоф, Дж., Пилипчук, М., ван Роой, Дж. М. и Войтащик, Дж. О. (2011, октябрь). Решение проблем со связностью, параметризованных по ширине дерева за одно экспоненциальное время. В Основы информатики (FOCS), 2011 IEEE 52-й ежегодный симпозиум (стр. 150-159). IEEE.

[2] Bodlaender, HL, Cygan, M., Kratsch, S. & Nederlof, J. (2013). Детерминированные алгоритмы с одним экспоненциальным временем для задач связности, параметризованных по ширине дерева. В Автоматах, Языках и Программировании (стр 196-207). Springer Berlin Heidelberg.

[3] Маркс Д. (2005). NP-полнота раскраски списка и расширения предварительного окраски по краям плоских графов. Журнал теории графов, 49 (4), 313-324.

[4] Маркс Д. (2009). Результаты сложности для минимальной суммы краевого края. Дискретная прикладная математика, 157 (5), 1034-1045.

[5] Nishizeki, T., Vygen, J. & Zhou, X. (2001). Задача о непересекающихся ребрах является NP-полной для рядов-параллельных графов. Дискретная прикладная математика, 115 (1), 177-186.

Большинство алгоритмов для графов ограниченной длины дерева основаны на некоторой форме динамического программирования. Чтобы эти алгоритмы были эффективными, нам нужно ограничить число состояний в таблице динамического программирования: если вам нужен алгоритм за полиномиальное время, то вам нужно количество состояний за полиномиальное значение (например, n ^ tw), если вы хотите покажите, что проблема в FPT, вы обычно хотите показать, что число состояний является некоторой функцией ширины дерева. Количество состояний, как правило, соответствует числу различных типов частичных решений при разбиении графа на некотором небольшом разделителе. Таким образом, задача на графах ограниченной ширины проста, потому что частичные решения, взаимодействующие с внешним миром через ограниченное число вершин, имеют только ограниченное число типов. Например, в задаче с независимым множеством тип частичного решения зависит только от того, какие граничные вершины выбраны. В задаче о гамильтоновом цикле тип частичного решения описывается тем, как подпути частичного решения соответствуют вершинам границы друг другу. Варианты теоремы Курселя дают достаточные условия для того, чтобы задача обладала тем свойством, что частичные решения имеют только ограниченное число типов.

Если на графах ограниченной ширины задача сложная, то обычно это происходит по одной из следующих трех причин.

1. В задаче есть взаимодействия, которые не отражены в графике. Например, Steiner Forest интуитивно интуитивно понятен на графиках с шириной дерева 3, так как пары источник-назначение создают взаимодействия между несмежными вершинами.

Элизабет Гасснер: проблема Штейнерского леса вновь. J. Дискретные алгоритмы 8 (2): 154-163 (2010)

Мохаммад Хоссейн Батени, Мохаммад Таги Гаджиагайи, Даниэль Маркс: Схемы аппроксимации для леса Штейнера на плоских графах и графах ограниченной длины деревьев. J. ACM 58 (5): 21 (2011)

2. Задача определена по краям графа. Тогда даже если часть графа прикреплена к остальной части графа через ограниченное количество вершин, может быть много ребер, падающих на эти несколько вершин, и тогда состояние частичного решения можно описать только путем описания состояния все эти края. Это то, что усложнило задачи в [3,4].

3. Каждая вершина может иметь большое количество разных состояний. Например, Capacitated Vertex Cover является W [1] -твердым параметризованным по ширине дерева, интуитивно, потому что описание частичного решения включает в себя не только указание, какие вершины разделителя были выбраны, но также указание, сколько раз каждая выбранная вершина разделителя была используется для покрытия краев.

Майкл Дом, Даниэль Локштанов, Сакет Саурабх, Ингве Виллангер: Емкостное Доминирование и Покрытие: Параметризованная Перспектива. IWPEC 2008: 78-90

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

Я думаю, что одним из таких примеров является проблема разреженного разреза. Задача равномерного разреженного разреза разрешима на графах ограниченной ширины дерева, но взвешенная задача разреженного разреза даже не аппроксимируема (лучше, чем 17/16) в графах ограниченной ширины дерева.

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

$G=(V,E)$$w:E(G)\rightarrow N$$E(S,V\setminus S) \subseteq E(G)$$S \subset V$$\frac{W(E(S,V\setminus S))}{|S||V\setminus S|}$$E'\subseteq E(G)$$W(E')=\sum_{e\in E'}w(e)$

Основной ингредиент состоит из двух вещей:

1. Дополнительные функции, как здесь весовая функция. Но все же есть некоторые проблемы с весовой функцией, которые не очень сложны в неориентированных графах ограниченной ширины дерева.

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

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