[問題案] Edge-Coloring of Bipartite Graphs

[maspypy]

雑に、置いておきます。ぜひどなたかにもらって欲しい案件。

(任意) 問題ID: {ID} 問題名: {Edge-Coloring of Bipartite Graphs}

参考資料: ・二部グラフの辺彩色数は \Delta(G) = \max_v \deg(v) に等しい。 https://mathworld.wolfram.com/KoenigsLineColoringTheorem.html ・catupper さんによるアルゴリズム解説（これは O(VE) かな） https://www.slideshare.net/catupper/ss-25736611 ・「Edge-Coloring of Bipartite Graphs」でぐぐると色々出てきて、 E\log \Delta(G)くらいにはなるっぽい。 ・問題例 AGC037-D、GCJ2020qual-E などで利用できる構築です。まぁフローでいけるんですけど。

問題概要

二部グラフが与えられる。 なるべく少ない色での辺彩色を構築せよ。

入力

出力

制約

とりあえず、マッチングを1つずつ取り去る方法と差別化できるとうれしい気分。

[maspypy]

snukeさんの調査速報 https://twitter.com/snuke_/status/1246630370415538176?s=21

[yosupo06]

見ました　計算量をまとめると D = max degree = chromatic number (\Deltaはgithubで書くには大変なので…)として

• O(M \sqrt(N) D) : 愚直にHopcroft-Karpをする
• O(M(V + D))？ : catupperさんの解説通りに愚直にパスを発見して塗り分ける　V < Dの場合はどうなるかな？

が素直なやつで、後はオーダーが落ちるやつが実用的に早いかという話で

• (1) : グラフを正則に変形する(定数倍: 謎)
• (2) : 偶数なら分割、奇数なら完全マッチングを見つける(定数倍軽そう)
• (3) : 完全マッチングを見つける(定数倍: 謎、Hopcroft-Karpより早いのか？)

といった感じでしょうか、まだ(2)しか理解してない…

[maspypy]

参考資料：O(M\log M) https://www.tau.ac.il/~nogaa/PDFS/lex2.pdf self-contained で実質1ページくらいなので、読みやすいです。

[yosupo06]

• N(L + R), M : 100,000(速度と応相談)
• 多重辺あり

入力 (参考: https://judge.yosupo.jp/problem/bipartitematching )

L R M
a b
a b
: 
a b

出力

K (=彩色数)
color_0
color_1
:
color_{M - 1}

がいいと思っています