Выражение ширины клика с логарифмической глубиной

15

Когда нам дается древовидная декомпозиция графа с шириной w , есть несколько способов сделать его «красивым». В частности, известно, что его можно преобразовать в разложение дерева, где дерево является двоичным, а его высота равна O ( log n ) . Это может быть достигнуто при сохранении ширины разложения не более 3 Вт . (См., Например, «Параллельные алгоритмы с оптимальным ускорением для ограниченной ширины дерева», автор Bodlaender и Hagerup). Таким образом, логарифмическая глубина - это свойство разложения дерева, которое мы можем получить почти бесплатно.граммвесО(журналN)3вес

Мой вопрос: существует ли подобный результат для clique-width или, возможно, контрпример. Другими словами, учитывая выражение ширины клика для с использованием k меток, всегда ли существует выражение ширины клика высоты O ( log n ) для G , которое использует не более f ( k ) меток? Здесь высота определяется естественным образом как высота дерева разбора выражения clique-width.граммКО(журналN)грамме(К)

Если утверждение, подобное приведенному выше, неизвестно, существует ли пример вершинного графа G с небольшой шириной клика k , так что единственный способ построить G с метками f ( k ) - это использовать выражение с большим глубина?NграммКграмме(К)

Майкл Лэмпис
источник
2
treewidth / cliquewidth wikipedia
vzn

Ответы:

5

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

Фактически возможно перебалансировать выражения ширины клика, чтобы они имели логарифмическую глубину. Результат приведен в статье «Операции с графами, характеризующие ширину ранга и выражения сбалансированных графов», авторы Courcelle и Kanté, WG '08. Я цитирую теорему 4.4 из статьи:

КК×2К+1

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

Майкл Лэмпис
источник
3
Первый результат, касающийся сбалансированных выражений ширины клика, получен Courcelle и Vanicat (DAM 131 (1): 129-150, 2003). Статья WG'07 обобщает методы, описанные в статье 2003 г., и дает достаточные условия для алгебры графов для получения сбалансированных выражений. Моя гипотеза состояла в том, что мы не можем избежать экспоненциального взрыва, но я никогда не пытаюсь доказать или опровергнуть это. По крайней мере, наша техника не может избежать экспоненциального взрыва.
М. Канте