Модульная декомпозиция и клик-ширина

15

Я пытаюсь понять некоторые понятия о модульной декомпозиции и графах ширины клика .

В этой статье («О P4-аккуратных графах») есть доказательство того, как решать задачи оптимизации, такие как число кликов или хроматическое число, с использованием модульной декомпозиции. Решение этих проблем путем составления (используя непересекающуюся сумму или непересекающееся объединение) двух графов G1, G2 легко, если вы знаете ответ для G1 и G2. Поскольку простые графы на разложении P4-аккуратных графов представляют собой ограниченные графы (т. Е. C5, P5 и т. Д.), Их легко решить для этого «базового случая», а затем решить для композиций. Следовательно, используя дерево декомпозиции, можно решить эти проблемы за линейное время.

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

Мой вопрос:

1- Эквивалентно ли говорить, что простые графы дерева разложения ограничены (как в случае P4-аккуратных графов) и говорить, что граф имеет свойство «Clique-Width» ограничено?

2- В случае, если ответом для 1 является НЕТ, то: Имеется ли какой-либо результат о классах графов с ограниченными граф-простыми числами (как в P4-аккуратных графах) и, таким образом, о задачах оптимизации, таких как число кликов, разрешимых за линейное время на всех этих классах ?

user2582
источник

Ответы:

18

Вы найдете вводный текст о ширине клика (сокращенно cwd) здесь: верхние границы ширины клика графиков (B. Courcelle и S. Olariu, DAM 101). Вы можете найти более свежие результаты в этом обзоре: Последние разработки на графиках ограниченной ширины клики (М. Камински, В. Лозин, М. Миланик, DAM 157 (12): 2747-2761 (2009))

Cwd - это показатель сложности, основанный на графовых операциях, которые обобщают конкатенацию слов. Бесконечные счетные графы могут иметь ограниченный cwd. Вы скажете, что множество (возможно, бесконечное) графов (конечных или счетных) имеет ограниченный cwd, если существует постоянная k такая, что любой граф в этом наборе имеет cwd не более k. Например, полные графы имеют cwd 2, дистанционные наследственные графы cwd не более 3, ...

1) Связь между cwd и modular-dec следующая: cwd (G) = max {cwd (H) | H простое в модульном деке G}. Следовательно, вы можете сказать, что cwd обобщает тот факт, что «графы простых чисел имеют ограниченный размер». Вы можете иметь графы с простыми графами неограниченного размера, но с ограниченными cwd.

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

Некоторые алгоритмические аспекты модульного dec изучаются здесь "Обзор алгоритмических аспектов модульной декомпозиции" (М. Хабиб и К. Пол, Обзор информатики 4 (1): 41-59 (2010))

М. Канте
источник
Однако я не уверен, полезны ли эти «линейные алгоритмы» на практике, поскольку в «Обзоре графов ограниченной ширины клика» (Шахин Камали) объясняется, что вам нужно для алгоритмов вводить k-выражения и получать это k-выражение. является NP-Hard.
user2582
4
Да, получение k-выражения является NP-полным, и эти алгоритмы имеют только теоретическое значение. Для некоторых из этих проблем (особенно проблем доминирования) существуют «лучшие алгоритмы». Однако для фиксированного k вы можете аппроксимировать cwd графиков cwd <= k. В этом алгоритме используется эквивалентная мера сложности ширины ранга (см., Например, этот обзор »П. Хлинены, С. Ум, Д. Сисе, Г. Готтлоб: Параметры ширины за пределами ширины дерева и их приложения. Comput. J. 51 (3 ): 326-362 (2008) "). Для некоторых классов графов cwd или верхняя граница cwd известны.
М. Канте