Ekspresi lebar klik dengan kedalaman logaritmik

Ketika kita diberi dekomposisi pohon dari grafik dengan lebar , ada beberapa cara di mana kita dapat membuatnya "bagus". Secara khusus, diketahui bahwa adalah mungkin untuk mengubahnya menjadi dekomposisi pohon di mana pohon itu biner dan tingginya adalah . Ini dapat dicapai sambil menjaga lebar dekomposisi paling banyak . (Lihat misalnya "Algoritma paralel dengan speedup optimal untuk treewidth terbatas", oleh Bodlaender dan Hagerup). Jadi, kedalaman logaritmik adalah properti dari dekomposisi pohon yang hampir bisa kita peroleh secara gratis.$G$$w$$O(\log n)$$3w$

Pertanyaan saya adalah apakah ada hasil yang sama untuk lebar klik, atau mungkin contoh tandingan. Dengan kata lain, diberikan ekspresi lebar-klik untuk menggunakan label , apakah selalu ada ekspresi lebar-klik dari tinggi untuk , yang menggunakan paling banyak label ? Di sini, ketinggian didefinisikan secara alami sebagai ketinggian pohon parse dari ekspresi lebar-klik.$G$$k$$O(\log n)$$G$$f(k)$

Jika pernyataan yang mirip dengan yang di atas tidak diketahui, apakah ada contoh grafik -vertex dengan lebar klik-kecil , sehingga satu-satunya cara untuk membangun dengan label adalah dengan menggunakan ekspresi dengan besar kedalaman?$n$$G$$k$$G$$f(k)$

Setelah beberapa saat saya menemukan jawaban dalam literatur, jadi saya mempostingnya di sini kalau-kalau itu berguna untuk orang lain.

Sebenarnya mungkin untuk menyeimbangkan kembali ekspresi lebar-klik sehingga mereka memiliki kedalaman logaritmik. Hasilnya diberikan dalam makalah "Operasi grafik yang mengkarakterisasi peringkat-lebar dan ekspresi grafik seimbang" oleh Courcelle dan Kanté, WG '08. Saya mengutip Teorema 4.4 dari makalah:

$k$$k \times 2^{k+1}$

Tangkapan di sini adalah bahwa jumlah label meledak secara eksponensial dalam penyeimbangan. Tampaknya untuk lebar klik tidak ada hasil yang lebih baik saat ini diketahui. Makalah yang sama memberikan hasil yang serupa dengan hanya ledakan konstan untuk rankwidth, tetapi ini tidak membantu, karena perbedaan antara lebar klik dan lebar pita dapat menjadi eksponensial dalam kasus terburuk.