Hypergraph st-最小割

01-30

剛剛submit了點和hypergraph有關的東西給SODA 2017(更新: 也被accepted了), 我主頁可以看到.

一些我們發現了但是感覺不足掛齒的結果, 也就沒有寫進去. 其中一個是hypergraph $st$ -最小割問題: 在hypergraph $H$ 上刪除最少的邊, 使得 $s$ 和 $t$ 不聯通. 以前各種文章里出現的做法都是下面這樣的:

轉換這個hypergraph到incidence graph. 每個代表邊的頂點都有capacity 1.
拆頂點, 獲得有向圖 $G$
跑st最大流在 $G$ 上.

這個方法也能用在有權值的hypergraph上. 假如 $H$ 有 $n$ 個頂點, $m$ 個邊, 頂點的度之和為 $p$ . 則 $G$ 有 $O(n+m)$ 個頂點, $O(p)$ 個邊. 跑最大流要 $O((n+m) p)$ 的時間, 而 $m$ 可能比 $n$ 大很多. 很多文章里也就把這個速度做為最好的速度了. 似乎裡面也有人問這是否是最優的.

有意思的是好像並沒有人知道(或者知道也懶得寫出來)實際上可以做的更好.

有一個簡單的Dinics algorithm + dynamic tree的最大流演算法演算法. (Sleator and Tarjan 1982), 叫這個演算法A的話.

Theorem: 用演算法A, $G$ 上最大流可以在 $tilde{O}(np)$ 時間算出.
Proof: $G$ 里最長的路徑的長度是 $O(n)$ , 每一次blocking flow, $s$ 和 $t$ 的距離增加至少1. 所以最多 $O(n)$ 次blocking flow, 而每一次blocking flow可以 $tilde{O}(p)$ 時間做到.

我們感覺這個很trivial而且和我們文章沒啥關係就懶得指出了.

Remark 當然, 有時候指出一些"顯然易見"的東西還是會幫助一些其他人的. 有一些人在研究一些網路安全的東西的時候, 遇到了一個優化問題. 他們的解法是用integer program或者heuristic. 而Yamaguchi等人發現了這問題不過是hypergraph最小割問題... 於是指出來了並且發在了一個IF 4+的地方. 哈哈哈這可是理論人想都不敢想的. (這裡提到IF純屬搞笑. 不代表作者的任何觀點.). [slides].

P.S. 有時候我也想知道其他領域有沒有啥東西我可以去幫忙解決.