что легко для второстепенных исключенных графов?

Приближение числа раскрасок, кажется, легко на второстепенных исключенных графах, используя алгоритм Юнга / Шаха. Каковы другие примеры проблем, которые сложны для общих графов, но просты для второстепенных исключенных графов?

Обновление 10/24 Кажется, следуя результатам Гроэ, формула, которая является FPT для тестирования на графах ограниченной ширины, является FPT для тестирования на второстепенных исключенных графах. Теперь возникает вопрос - как это связано с возможностью подсчета удовлетворяющих заданий такой формулы?

Вышеприведенное утверждение неверно. MSOL является FPT на ограниченных графах ширины дерева, однако 3-окрашивание является NP-полным на плоских графах, которые исключены незначительно.

Наиболее общий результат известен Грохе. Резюме было представлено в июле 2010 года:

• Мартин Грох, Определимость с фиксированной точкой и полиномиальное время на графах с исключенными несовершеннолетними , LICS 2010. ( PDF )

Короче говоря, любое выражение, которое можно выразить в логике с фиксированной точкой со счетом, имеет алгоритм полиномиального времени на классах графов с хотя бы одним исключенным минором. (FP + C - логика первого порядка, дополненная оператором с фиксированной точкой и предикатом, который дает мощность определяемых множеств вершин). Основная идея заключается в том, что исключение минора позволяет графам в классе иметь упорядоченные древовидные разложения, которые можно определить в логике с фиксированной запятой (без подсчета).

Таким образом, большой класс ответов на ваш вопрос можно получить, рассматривая свойства, которые можно определить в FP + C, но которые трудно сосчитать.

Изменить: я не уверен, что это на самом деле отвечает на ваш вопрос, тем более для вашего обновления. Указатель на результат Грохе и его утверждение верны, но я не думаю, что вычеркнутый текст имеет отношение к вашему вопросу. (Спасибо Стефану Кройцеру за указание на это.) Возможно, стоит уточнить: хотите ли вы проблему подсчета, которая сложна в целом, но проста в классах, не включенных в класс, или проблему решения?

Интересным свойством семейств минор-замкнутых графов является то, что они имеют ограниченное вырождение . Это означает, что все задачи, которые являются легкими на графах ограниченного вырождения, являются легкими на графах из минор-замкнутого семейства.

$O(n^k)$$O(k d(G)^k n)$

Другие примеры можно найти в этом ответе Дэвида Эппштейна на MathOverflow на аналогичный вопрос о графах с ограниченным вырождением.

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

Алгоритм линейного времени для поиска разделителя в графе, исключая несовершеннолетнего , Брюс Рид и Дэвид Р. Вуд, ACM Transactions on Algorithms, 2009,

$O(n^{2/3})$$O(n^{3/2} + m)$$O(n^{1/2})$

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

$O(1)$

Незначительная теория алгоритмического графа: декомпозиция, аппроксимация и раскраска Демейна, Хаджиагайи и Каварабаяси

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

$K_5$$K_{3,3}$

$H$$H$

$K_t$$(t-1)$$K_t$$(t-1)$$t− 2$