On Sparse Graphs with Dense Long Paths

論文の主定理は以下の通り

どんな $n$ 頂点を取り除いても長さ $n$ のPathが残るようなDAGの辺数を $m$ とし、 $f(n) = \min m$ とすると

$c_1 n\log n / \log \log n \lt f(n) \lt c_2 n \log n$

が成り立つ。

Corollary

どんな $n$ 頂点を削除しても、 $n$ 本の辺を含む連結成分が存在するような無向グラフが $m$ 辺をもつとし、 $f(n) = \min m$ とすると、

$f(x) \lt c_2 n$

が成り立つ。 $n$ 本の辺を含む連結成分、の部分は大きさ $n$ の連結成分、に置き換えてもよい（定数は変わるが）

任意の $\varepsilon \lt 0$ について、ある定数 $c$ が存在し、任意の $n$ について $O({}_{{}_{(2 + \varepsilon)n}C_2}C_{cn})$ 個のグラフを除いた $(2 + \varepsilon)n$ 頂点 $cn$ 辺のグラフは、どんな $n$ 頂点を取り除いたとしても、大きさ $n$ 以上の連結成分が残る。

Related Theoremで主定理を使うかと思ったけどとくに関係なかった。確率的な議論をして証明している。

要は、辺のオーダーが頂点の定数倍であるようなSparseなグラフでもいいSeparatorが存在するとは限りませんよ、という話。

A Separator Theorem for Planar Graphs

Separtorという概念は平面グラフに限らず、グラフに一般的なもので、たとえば二分木はある一辺をseparatorとして、残りの成分がすべて2/3以下のコストをもつようにすることができる。一般の木は一頂点をseparatorとして同様のことができる。

上の論文でも触れたとおり、一般のsparseなグラフに関していつも $o(n)$ のseparatorが存在するかと言われるとそうではない。

この論文では平面グラフで $O(\sqrt n)$ のseparatorが存在することを示している。全域木をとって、全域木に含まれない辺を1本追加したときにできるサイクルで、サイクルの内側と外側を両方コスト2/3以下にするようなサイクルが存在することを示している。

いろいろなパターンに場合分けして示している感じ。実は平面グラフよりも広いクラスについても適用可能で、finite element graphとよばれる、平面グラフの平面への埋め込みを考えたときに、各面について、可能な対角線をすべて引いてcliqueを作ったものに関しても似たようなことをやっている（オーダーは $O(\sqrt n)$ ではなく $k$ をboundary vertexの上限として $O(k\sqrt n)$ なので別に任意のグラフについて $O(\sqrt n)$ という主張にはなっていなそう）