Когда нам дается древовидная декомпозиция графа с шириной w , есть несколько способов сделать его «красивым». В частности, известно, что его можно преобразовать в разложение дерева, где дерево является двоичным, а его высота равна O ( log n ) . Это может быть достигнуто при сохранении ширины разложения не более 3 Вт . (См., Например, «Параллельные алгоритмы с оптимальным ускорением для ограниченной ширины дерева», автор Bodlaender и Hagerup). Таким образом, логарифмическая глубина - это свойство разложения дерева, которое мы можем получить почти бесплатно.
Мой вопрос: существует ли подобный результат для clique-width или, возможно, контрпример. Другими словами, учитывая выражение ширины клика для с использованием k меток, всегда ли существует выражение ширины клика высоты O ( log n ) для G , которое использует не более f ( k ) меток? Здесь высота определяется естественным образом как высота дерева разбора выражения clique-width.
Если утверждение, подобное приведенному выше, неизвестно, существует ли пример вершинного графа G с небольшой шириной клика k , так что единственный способ построить G с метками f ( k ) - это использовать выражение с большим глубина?
Ответы:
Через некоторое время я нашел ответ в литературе, поэтому я публикую его здесь на случай, если он пригодится кому-то еще.
Фактически возможно перебалансировать выражения ширины клика, чтобы они имели логарифмическую глубину. Результат приведен в статье «Операции с графами, характеризующие ширину ранга и выражения сбалансированных графов», авторы Courcelle и Kanté, WG '08. Я цитирую теорему 4.4 из статьи:
Загвоздка в том, что количество баллонов увеличивается в геометрической прогрессии при балансировке. Похоже, что для ширины клики лучшего результата в настоящее время не известно. В той же статье дается аналогичный результат с постоянным увеличением ширины ранга, но это не помогает, поскольку разница между шириной клика и шириной ранга может быть экспоненциальной в худшем случае.
источник