[問題案] Tree Decomposition (Treewidth 2)

[yosupo06]

(任意) 問題ID: Tree Decomposition (Treewidth 2) 問題名: tree_decomposition_of_treewidth_2

参考(Tree decomposition): https://en.wikipedia.org/wiki/Tree_decomposition 参考(AOJ ICPC, 外平面グラフ): http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2405 参考(↑の講評 具体的な木分解の構成法が乗っている): https://jag-icpc.org/?plugin=attach&refer=2012%2FPractice%2F%E6%A8%A1%E6%93%AC%E5%9B%BD%E5%86%85%E4%BA%88%E9%81%B8%2F%E8%AC%9B%E8%A9%95&openfile=ports.pdf

問題概要

N頂点M辺の木幅が1, 2の単純な無向グラフが与えられる。木分解を構成

具体的には木を作る　木の頂点はそれぞれバッグ(元のグラフの部分集合)を持つ

• バッグのサイズはすべて3以下
• 元のグラフの各辺(u, v)について、uとvを両方バッグに含む木の頂点が存在する
• 元のグラフの各頂点uについて、uをバッグに含む木の頂点のみを取り出したとき、それらの部分誘導グラフが連結(or 空グラフ)

入力

N M
u_0 v_0
u_1 v_1
:
u_{M - 1} v_{M - 1}

出力

K
l_0 x_0 x_1 x_{l_0 - 1}
l_1 x x x
:
l_{k - 1} x x x
a_0 b_0
a_1 b_1
:
a_{K - 2} b_{K - 2}

制約

N <= 100,000

検討事項

• 木の頂点数の制約(大きめに取る？)
• 木分解に制約を課す？(例: Nice Tree Decomposition)

[yosupo06]

https://pacechallenge.wordpress.com/pace-2017/track-a-treewidth/ PACE-2017 木分解の一般的なフォーマット

[yosupo06]

https://dl.acm.org/doi/pdf/10.1145/167088.167161

[yosupo06]

https://www.graphclasses.org/classes/gc_899.html

https://ei1333.hateblo.jp/entry/2020/02/12/150319

[yosupo06]

https://pdfs.semanticscholar.org/84ac/739385ee34066e9a5e14795606dfde29bfe9.pdf

[beet-aizu]

K ≤ 2N+M+10、きつい　https://judge.yosupo.jp/submission/9898 @ei1333 Nice Tree Decompositionって頂点数どれくらいになりますか

[beet-aizu]

3N+M+10あれば足りそう　https://judge.yosupo.jp/submission/9901

[beet-aizu]

outer_planer でバグってるのかと思ったら非連結なケースがouter_planerだけだったぜ！

[yosupo06]

記憶をなくしたんですが、2N + M + 10ではなさそうです　小さくて困ることはないのでもう10N + M + 10とかでいい気がする(10sで10N + M + 10行出力できるかはともかく…)