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