A simple max-cut algorithm for planar graphs

e-archive.informatik.uni-koeln.de

を読んだ。

https://icpc-girigiri.slack.com/archives/GJM417MNV/p1566016527000100

にファイルがある。

概要

平面グラフのmax-cutをmaximum weighted matchingに帰着させて解いている。平面グラフのmaximum weighted matchingがで解けることからmax-cutもこの計算量で解ける。

アルゴリズム

1. 連結な単純グラフが入力として与えられたとき、まずの双対グラフをとる。双対グラフの辺のコストは、その辺が横切る元のグラフの辺のコストと同じにする。の次数5以上の頂点を分割し、分割した頂点同士をコスト0の辺でつなぐ。さらに、の各頂点をに置き換えたグラフを考える。内部の辺の重みは0.

2. 以上のグラフでmaximum weighted matchingを考える。必ずperfect matchingが存在することが示せ、このとき、各に着目すると必ずから外に出る辺は偶数本になっていることがわかり、perfect matchingはEulerianになることがわかる。

3. 双対グラフでのEulerian subgraphと元のグラフのカットには1対1対応があり、この最大重みeulerian subgraphが元のグラフでの最大cutになっている。

計算量

平面グラフを三角形分割したものを考えると、辺の数や面の数が超点数のオーダーで抑えられる。そうすると面の数も頂点数オーダーになる。双対グラフの頂点数、辺数も従って元のグラフの頂点数オーダーで、をとってもオーダーは不変。あとはmaximum weighted matchingだが、これはTarjanによると