https://noshi91.hatenablog.com/entry/2024/05/31/012055

概要

$n$ 要素の集合を $2$ つに分割することを $\log _ 2 n$ 回行って、どの $2$ 要素もどこかで分離されているようにすることができる。向きの付いた分割についても同様の問題を考え、それぞれの構成法と最適性を示す。

向きの無い分割

問題例

無向グラフ $( V, E )$ があり、各辺には正の重みが付いているとする。 $U \subseteq V$ が与えられるので、 $u, v \in U, \, u \neq v$ の条件下で $u , v$ 間の距離の最小値を求めよ。

解法

この問題は Dijkstra 法に少し手を加えると $\mathrm O ( M \log M )$ で解くことができるが、ここではその解法は思い浮かばなかったことにする。

$U$ を始点とする Dijkstra 法を行うと、どの $v \in U$ に対しても $v$ への距離は $0$ となってしまうため上手く行かない。そこで $S \subseteq U$ を取り、 $S$ を始点とし $U \setminus S$ を終点とする距離を求める。もし最適な $u, v$ が $\lbrace S , U \setminus S \rbrace$ によって分離されているなら、すなわち $\lvert \lbrace u , v \rbrace \cap S \rvert = 1$ を満たすなら、これで最適値が得られる。 $S$ を一様ランダムにとれば $1 / 2$ の確率でこれは達成されるが、決定性アルゴリズムを得たい。定式化すると以下のようになる。

問題

集合 $U$ に対し、以下の条件を満たす集合族 $\mathcal S \subseteq 2 ^ U$ を構成する。

任意の $x , y \in U, \, x \neq y$ に対し、ある $S \in \mathcal S$ が存在して、 $\lvert \lbrace x , y \rbrace \cap S \rvert = 1$

$\lvert \mathcal S \rvert$ は $\lvert U \rvert$ に対しどこまで小さくできるか？

構成と最適性

各 $x \in U$ に対し、 $T _ x := \lbrace S \in \mathcal S \mid x \in S \rbrace$ と定義する。すると問題の条件は、任意の $x , y \in U, \, x \neq y$ に対して $T _ x \neq T _ y$ と言い換えることができる。 $\lvert U \rvert \gt 2 ^ {\lvert \mathcal S \rvert}$ なら鳩の巣原理によりこの条件は満たされることはなく、逆に $\lvert U \rvert \leq 2 ^ {\lvert \mathcal S \rvert}$ ならば各 $T _ x$ が $\mathcal S$ の相異なる部分集合になるように $\mathcal S$ を定めることができる。よって $\lvert \mathcal S \rvert = \lceil \log _ 2 \lvert U \rvert \rceil$ が最適である。

元の問題例は $\mathrm O (M \log M \log \vert U \rvert)$ で解けることになる。

向きの付いた分割

この節は ICPC 2023 World Finals Luxor に出題された問題の解法を基に執筆しています。

問題例

有向グラフ $( V, E )$ があり、各辺には正の重みが付いているとする。 $U \subseteq V$ が与えられるので、 $u, v \in U, \, u \neq v$ の条件下で $u \to v$ の距離の最小値を求めよ。

解法

有向グラフになったため、最適な $u, v$ に対し $u \in S, \, v \notin S$ を満たす必要がある。定式化すると以下のようになる。

問題 (ICPC 2023 WF 改題)

集合 $U$ に対し、以下の条件を満たす集合族 $\mathcal S \subseteq 2 ^ U$ を構成する。

任意の $x , y \in U, \, x \neq y$ に対し、ある $S \in \mathcal S$ が存在して、 $x \in S, \, y \notin S$

$\lvert \mathcal S \rvert$ は $n := \lvert U \rvert$ に対しどこまで小さくできるか？

構成と最適性

前節と同様に、各 $x \in U$ に対し $T _ x := \lbrace S \in \mathcal S \mid x \in S \rbrace$ と定義する。すると問題の条件は、任意の $x , y \in U, \, x \neq y$ に対して $T _ x \nsubseteq T _ y$ と言い換えることができる。 $\lvert \mathcal S \rvert$ を固定した際にこのような $T _ x$ が最大でいくつ取れるかという問題の解答は Sperner の定理として知られており、 $T _ x$ として大きさ $\lfloor \lvert \mathcal S \rvert / 2 \rfloor$ の $\mathcal S$ の部分集合を選べばよい。したがって、 $\binom d { \lfloor d / 2 \rfloor } \geq \lvert U \rvert$ となる最小の $d$ が $\lvert \mathcal S \rvert$ の最小値である。 $d \in \log _ 2 \lvert U \rvert + \mathrm O ( \log \log \lvert U \rvert )$ であり、例えば $\lvert \mathcal S \rvert = 21$ で $\lvert U \rvert = 3.5 \times 10 ^ 5$ 程度まで構成できる。