川渡り問題の一般化を考える ② アルクイン数と実装

投稿:2025/11/30 更新:2025/12/02

前回の記事
川渡り問題の一般化を考える

この記事で紹介する定理やその証明はCsorba, Hurkens, Woeginger (2012) の論文に基づいている。

文章はものすごく雑

情報の整理

前回の記事の内容

一般化川渡り問題を禁止制約$G(S,F)$とボートサイズ$B$で表現
$G(S,F)$が与えられたときの川渡りが達成可能な最小の$B$をアルクイン数と呼ぶ
アルクイン数はこの2択。　$Boat(G) = \begin{cases}\tau(G) \\ \tau(G)+1\end{cases}$
アルクイン数の計算はNP困難

論文の表現に合わせて、$Boat(G)=\tau(G)$のとき小舟グラフ、$Boat(G)=\tau(G)+1$のとき大舟グラフと呼ぶ。

最小ボートサイズを決定する

最小頂点被覆は分かっているので、小舟グラフなのか大舟グラフなのかを判別するだけ。

使う記号
$V$: グラフの全頂点集合($|V|=N$)
$C$: グラフの最小頂点被覆(の一つ)
$I$: グラフの最大独立集合($C$に対応する補集合)
$N(v)$: 頂点vに隣接している頂点の集合
$N(A)=\cup_{u\in A}{N(u)}$: 集合Aに隣接している頂点集合
$\overline{N}(A)$: 集合Aに隣接していない頂点集合
$N_B(A)= N(A) \cap {B}$ : Bの中で集合Aに隣接している頂点集合

戦略から考える

実際に$Boat(G)=|C|$で達成を目指す戦略を考えてみる。

まず思いつきそうなのがこれ。
最小頂点被覆を運んで1つ以上降ろす。それ以外をずっとボートに乗せながら可能な限り右岸に運んで、最後に頑張る。

Cの部分独立集合Xを取る。
C-XをYとする。($X\cup Y=C, X\cap Y=\emptyset$)

左岸→: Cを運ぶ

←右岸: Yを運ぶ。(右岸にはXが残っていて、舟には|X|の空きがある)

左岸→: |X|の空きを使ってXに隣接しない頂点を往復して全て運ぶ

←右岸: Yを運ぶ

(この時点で左岸には、|C|以外でXに隣接する頂点が全て残っている)

左岸→: |X|の空きを使って適当に乗せるだけ運ぶ

←右岸: Cを運ぶ (右岸にXを残すと条件に反してしまうため)

左岸→: 左岸にXをおろし、|X|の空きを使って残りを全て運ぶ

(このとき、残りをすべて運べないならば条件に違反する。)

←右岸: Yを運ぶ

左岸→: Cを運ぶ

終了。

(このとき、残りをすべて運べないならば条件に違反する。)

こうなるのは、C以外でXに隣接する頂点数が$2|X|$より多い場合である。 (|X|の空きを使って、「X隣接を右に、Xを左に、X隣接を右に」のように運んでいるため)
よって以下のことが言える。

Cの部分独立集合Xであって、$2|X| \ge (N_I(X) )$が成り立つものが存在する時、$Boat(G)=|C|$である。

これは十分条件であって必要条件ではない。
といっても最適戦略はこの戦略に一捻り加えるだけで導ける。
ステップ8の段階で、降ろすのをXではなく任意の独立集合Yに変えても良い。もし、残りの$N_I(X)$のうち、Yに隣接しているものが無いならばそれを一緒に左に残しても良いので、2回で全部運びきらなくても許されるようになる。以降ステップ3と同様に往復すれば必ず達成することができるため、要となるのはステップ8の段階でCの残す独立部分集合XとY($X=Y$でも良い)の「入れ替え」が可能かどうか。
今、Xに隣接してない頂点はステップ3で全部運びきってるので、 Xにのみ隣接している頂点とXかつYに隣接している頂点のみが左岸に残っている。 Yに入れ替えた後はXに隣接している頂点はどうでもよいので、入れ替え時に重要なのはXかつYに隣接している頂点の数。
ほぼ答えにたどり着いたので、もう公式書く

分類定理

C内の部分独立集合の組S,Tであって、$|N_{U}(S)\cap N_{U}(T)|<=|S|+|T|$を満たすようなものが存在する時、またその時に限り$Boat(G)=|C|$である

これが必要条件であることの証明はこの記事ではしない。詳しい証明は以下の論文を確認してほしい。
十分性は先程の戦略からしめせる。

先の戦略で言うと、
Sが最初に右岸に放置する集合、Tが入れ替え後に左岸に放置する集合を表していて、条件式は、右岸にTのみ隣接とSがある状態から、Sを回収し、SかつT隣接を右岸に運んで、左岸にTを置く過程を表している。後に手順を復元するコードも紹介するのでそれを見れば想像つくかも。

実装

指数時間アルゴリズムだが、それは仕方がない。
まず最小頂点被覆Cを求める。
これはよく知られている枝刈りバックトラッキングで、$O(1.??^N)$で求めることができる。
指数時間アルゴリズム入門 | PPTによると$O(1.446^N)$だとか。これは古い情報なので、実際はもっと軽かったとか証明されてたはずだが、探すのは面倒なので1.446ということにする。(そしてなぜかリンク先が閉鎖している。1年前は動いてたはず...)

最悪ケースはわからないが、高速な言語を使えばN=100でも大体すぐ実行が終わる。
(ちなみにLibrary Checker(N<=40)にC++で提出すると4msecだった)

先程の判定式を利用して、Cの部分独立集合のペアS,Tを全探索する。

本質的な改善にはならないが、愚直の$O(4^{|C|}NM)$から$O(4^{|C|}+N)$に落としてみる
集合をintの2進表現で持つ。
前計算として、各集合に対しての隣接集合と独立集合であるかのフラグを求めておく。
これはどちらも、bitdpとbit演算で $O(2^{|C|})$で可能($2^{|N|}$がword sizeに収まる前提)
これで集合S,Tを固定したときのそれが独立集合であるかの判定と、$|N_{U}(S)\cap N_{U}(T)|$が$O(1)$で求められるようになった。

ソースコードを一応貼っておく

def maximal_independent_set(g: list[int], d: int = 0) -> int:
    g = g[:]
    n: int = len(g)
    ret: int = 0
    v: int = -1
    ma: int = -1
    for i in range(n):
        if not (d & (1 << i)):
            if g[i].bit_count() <= 1:
                v = i
                break
            if g[i].bit_count() > ma:
                ma = g[i].bit_count()
                v = i
    if v == -1:
        return ret
    d |= 1 << v
    for i in range(n):
        g[i] &= ~(1 << v)
    if g[v].bit_count() > 1:
        vs: int = maximal_independent_set(g[:], d)
        if ret.bit_count() < vs.bit_count():
            ret = vs
    for i in range(n):
        if g[v] & (1 << i):
            d |= 1 << i
            for j in range(n):
                g[j] &= ~(1 << i)
    vs = maximal_independent_set(g[:], d)
    vs |= 1 << v
    if ret.bit_count() < vs.bit_count():
        ret = vs
    return ret


def minimal_vertex_cover(g: list[int]):
    return ~maximal_independent_set(g) & ((1 << len(g)) - 1)


# bitの隣接リストをください
def get_alcuin_number(G: list[int]) -> int:
    mvc: int = minimal_vertex_cover(G)
    C: list[int] = [i for i in range(len(G)) if mvc & (1 << i)]

    L: int = len(C)
    to_orig: list[int] = [0] * (1 << L)
    neighbors: list[int] = [0] * (1 << L)
    is_independent: list[bool] = [False] * (1 << L)
    is_independent[0] = True
    inds: list[int] = []
    for mask in range(1, 1 << L):
        msb: int = mask.bit_length() - 1
        pre = mask & ~(1 << msb)
        to_orig[mask] = to_orig[pre] | (1 << C[msb])
        neighbors[mask] = neighbors[pre] | G[C[msb]]
        if is_independent[pre] and not neighbors[mask] & to_orig[mask]:
            is_independent[mask] = True
            inds.append(mask)

    for S in inds:
        for T in inds:
            if (
                neighbors[S] & neighbors[T] & ~to_orig[-1]
            ).bit_count() <= S.bit_count() + T.bit_count():
                return len(C)
    return len(C) + 1

[!Question]

なぜ低速なPythonを使っているのか？

誰にだってそういう時期はある

ちなみにこれは計算量が最小頂点被覆の大きさに依存するFPTアルゴリズムで、Nが非常に大きいケースでもCが小さければ高速に判定できる。
(先程書いた判定式を利用しなくても川渡り過程の全状態を持ったbfsで解くことができるが、雑に見積もって$O(4^N)$枝刈りで相当落ちるかもだが、FPTではない上形式的な解法のほうが後々嬉しいので今回は使わない。最小往復回数とかを求めたいときはbfsのほうが適してそう)

手順の復元

S,Tが求まれば、後は戦略通りにシミュレーションするだけなので頑張る。
先の分類定理で条件を満たすS,Tが存在しなかった場合それは大舟グラフである。
前回の記事で述べた通り、$B=\tau(G)+1$なら最小頂点被覆を常に乗せながら、残りの頂点を1つずつ運んでいくだけ。実装するとこうなる。


moves:list[list[int]]=[] # moves[i]: i回目の移動でボートに乗せる頂点集合
boat: int = len(C) + 1
for i in range(N):
	if not (mvc >> i) & 1: # mvcは最小頂点被覆に含まれる頂点番目のbitが立っているint変数
		moves.append(C + [i])
		moves.append(C)
moves.pop()

S,Tが存在した場合、小舟グラフである。先の面倒な戦略を頑張って実装する。

# 下準備
S: list[int] = bit_to_ones(s) # Sに含まれる頂点集合
S_comp: list[int] = bit_to_ones(~s & mvc) # Cのうち、Sに含まれない頂点集合
T: list[int] = bit_to_ones(t) # Tに含まれる頂点集合
T_comp: list[int] = bit_to_ones(~t & mvc) # Cのうち、Tに含まれない頂点集合

nst: list[list[int]] = [[], [], [], []] # I(最大独立集合)の各頂点を、S,Tに隣接するかどうかの2bitで分類したリスト
sn = neighbors[-1] & ~mvc
tn = neighbors[-1] & ~mvc
for i in range(N):
	if not (mvc >> i) & 1:
		x = 0
		if (sn >> i) & 1:
			x |= 1
		if (tn >> i) & 1:
			x |= 2
		nst[x].append(i)
nst[2].extend(nst[0]) # S,Tどちらにも隣接しない頂点はTに隣接していることにしてサボる(S隣接、T隣接、ST隣接の三通りしかいらず、重要なのはST隣接のサイズだけなので)

# シミュレーション開始
moves:list[list[int]]=[]
boat:int = len(C)
moves.append(C)
moves.append(S_comp) # Sを右岸に置いて戻る

# Sに隣接せずTに隣接している頂点を全て運び切る(右岸にはSしかないので可能)
for i in range(0, len(nst[2]), len(S)):
	moves.append(S_comp + nst[2][i : i + len(S)])
	moves.append(S_comp)

# 入れ替えを行う
moves.append(S_comp + nst[3][0 : len(S)]) # 空き|S|を使ってSかつTに隣接している頂点を右岸に運ぶ
moves.append(C) # ここでSを左岸に戻す(戻さないと違反するので)
moves.append(T_comp + nst[3][len(S) : len(S) + len(T)]) # ここで初めてTを左岸に置いて、空き|T|を使ってSかつTに隣接している頂点を右岸に運ぶ(二回目)
moves.append(T_comp)

# 左岸に残っている、Tに隣接せずSに隣接している頂点を運び切る
for i in range(0, len(nst[1]), len(T)):
	moves.append(T_comp + nst[1][i : i + len(S)])
	moves.append(T_comp)

moves.append(C)

ちょっと長いのでこれまでの全てのコードをgistに投稿した。
最小ボートサイズと手順をくれる完全なプログラム付き。
solve.py · GitHub

特定のグラフクラスでの高速化

辺数が少ない場合

find_STを高速化できる。
例えば、S,Tに同じ1頂点を選ぶケース、隣接頂点が2以下なら即時Yesなので、鳩の巣原理より、グラフ全体の辺の本数が$2|C|$以下なら確定。O(N)で判定できる。
こんな感じで色々計算してみると、
$min\left( 5|C|, 3|C|+\frac{|C|(|C|-1)}{2} \right)$
辺の本数がこれ未満なら即座に小舟グラフであるとわかったりする。
実装においては変なことをしなくても探索順をS,Tともに頂点数が少ないペアやS=Tのペアのような、パターンが少ないものを優先的に探索するだけでよい。この工夫は簡単な割に強力で、多くのケースでは実際に$O(4^{|C|})$かけなくても$O(|C|)$や$O(|C|^2)$で即座に判定できたりする。

木の場合

木の場合は簡単。
論文にはスプリットグラフがなんちゃらコードラルグラフがなんちゃら小難しい証明が書かれていたが、先程の分類定理を使えばすぐに分かる。

木の最小頂点被覆Cのサイズで場合分けする。
$|C|\ge2$:の場合、C内の任意の異なる頂点u,vを取り出し、$S={u},T={v}$として分類定理を適用する。木の性質より、異なる2頂点の共通隣接頂点は高々1つであるため、常に小舟グラフである。
$|C|=1$の場合、
これはスターグラフである。$v\in C, S={v}, T={v}$とするしかないので、共通隣接頂点数が2以下になるのは、頂点数が3以下ののスターグラフだけである。

よって頂点数が4以上のスターグラフのみ大舟グラフ
それ以外は小舟グラフ。

実装においては、先程の「辺数が少ない場合」の探索順を工夫する高速化を利用するだけでよく楽。

平面グラフの場合

これが面白くて、最小頂点被覆を求める部分はNP困難だが、最小頂点被覆が分かっている上で小舟グラフか大舟グラフかどうかを判定する部分は多項式時間で計算できる。

定理: 最小頂点被覆のサイズが5以上の平面グラフはすべて小舟グラフである。

これを証明する。

最小頂点被覆Cから5つの頂点を取り出し、$Y={y_1,\dots,y_5}$と置く。
$1\le i<j\le 5$であって、$y_i$と$y_j$の共通隣接頂点数が2以下となるi,jのペアが存在すると、$S={y_i}, T={y_j}$で分類定理を適用すれば小舟グラフと確定する。
なので最小頂点被覆数が5以上であってそのどの2ペアの共通隣接頂点数も3以上であるような平面グラフを作りたいが、これが作れないことを示す。

$y_1,y_2$には最低3つの共通隣接頂点a,b,cを含む必要がある。これによって領域は3つに分割される。

  graph LR
	y1 <--> a
	y1 <--> b
	y1 <--> c
	a <--> y2
	b <--> y2
	c <--> y2

残りの、$y_3,y_4,y_5$は同じ領域内に含める必要がある。
なぜなら、例えば領域$y_1-a-y_2-b$に$y_3$を、領域$y_1-b-y_2-c$に$y_4$を配置すると$y_3,y_4$の共通隣接頂点はbの1つしかありえないので、$S={y_3},T={y_4}$とすることで分類定理より即座に小舟グラフと確定するから。

$y_3,y_4,y_5$を同じ領域に配置することにすると、それらはa,b,cのうちいずれかの1頂点には触れられなくなる。例えばabの間に配置するならc、bcの間ならa、acの間(外側)ならbが。言い換えると、$y_1,y_2,...,y_5$のうち$y_1,y_2$にしか隣接しない共通隣接頂点が必ず1つ存在する。
これは$y_1,y_2$以外にも言えることなので、任意のペア$y_i, y_j$について他の3頂点には隣接しない、共通隣接頂点$z_{ij}$が必ず存在する。
結果として、頂点集合$y_1,...,y_5$と任意の2ペアに対応する(uniqueな)$z_{i,j}$によって$K_5$の細分が形成される。
($y_i-z_{ij}-y_j$こういうパスが必ず存在しないといけなくて、これは$y_i-y_j$に$z_{ij}$を乗せただけの形なので)
オイラーの定理より$K^5$は平面グラフではないことからこのグラフは構成できない。
終了。

最小頂点被覆のサイズが4以下の場合は必ずしも小舟グラフとは限らない。例えば以下のような大舟グラフが考えられる

import networkx as nx
G = nx.Graph()
for i in range(22):
    G.add_node(i, color='red' if i < 4 else 'lightblue')
g = [0]*22

def add_edge(u:int, v:int):
    G.add_edge(u,v)
    g[u]|=1<<v
    g[v]|=1<<u

now = 4
for i in range(4):
    for j in range(i):
        for _ in range(3):
            add_edge(i, now)
            add_edge(j, now)
            now += 1

print(get_alcuin_number(g))
print(minimal_vertex_cover(g).bit_count())
print(nx.is_planar(G))

# 出力
# 5
# 4
# True

まぁ|C|が4以下なら$4^{|C|}$部分は定数として見做せるため一般グラフの判定法を使えばよい。

実装においては、木と同じく先程の探索順を工夫する高速化を利用するだけで良い。
これも木と同じくS,Tの要素数が小さいケースで判例が作れるよ～って定理なので、定理が簡単であればあるほど高速に動作しやすいみたいなのはあるかも(正確ではないが)

二部グラフの場合

アルゴリズムは一番面白い。
木や平面グラフの時と違って、シンプルな定理があるわけでなく、実装も少し重い

条件を満たす独立集合S,Tを探す問題を、最大独立集合を求める問題に言い換える。
分類定理は以下のように変形できる

$$ \begin{aligned} |N_I(S)\cap N_I(T)|\le |S|+|T| \\ |I|-|\overline{N}_I(S)\cup \overline{N}_I(T)| \le |S|+|T| \\ |I| \le |S|+|T|+|\overline{N}_I(S)\cup \overline{N}_I(T)| \end{aligned} $$

左辺は固定なので右辺の最大化を目指したい。
任意の極大独立集合が右辺に対応するようなグラフを作る。
$|S| \cup |\overline{N}_I(S)|$は独立集合で、$|T| \cup |\overline{N}_I(T)|$も独立集合。SとTは交わってても良いので独立に考えたい。なのでグラフGを2つにコピーして$G'$と$G''$をあわせた$H$を考える。Sは$G'$側、Tは$G''$側とすると、$S\cup T$は独立集合ということにできる。
ただし、$G'$と$G''$の元の$G$を考えた時に$\overline{N}_I(S)$と$\overline{N}_I(T)$が被ってしまう可能性がある。式は$|\overline{N}_I(S)\cup \overline{N}_I(T)|$で同じ頂点は一回しか数えられないようにしたいので、$G'$と$G''$の間の対応する$I$同士に辺を貼ることで解消する。
($G'$と$G''$は、各$v\in I$について$v'$と$v''$の間に辺が張られて繋がっている形状)

このグラフHから任意の極大独立集合(最大とは限らない自分を部分グラフとして含むような独立集合が自分以外に存在しないような集合)$MIS$を取ると、
$S=MIS \cap C'$
$T=MIS \cap C''$
$|\overline{N}_I(S)\cup \overline{N}_I(T)|=MIS\cap (I' \cup I'')$
と対応していることがわかり、Hの最大独立集合のサイズを求める問題に言い換えることができた。
S,Tが空でないという条件は$N^2$かけて1つの要素を固定して隣接する頂点を除いたグラフで考えれば良い。
$G$が二部グラフなら$H$も二部グラフなので、二部グラフの最大独立集合となり、二部グラフの最大マッチングに帰着でき、多項式時間で解くことができる。

(これらの言い換えは別に一般グラフでも使える(最大独立集合が多項式時間で求められないので本質的な高速化にならないが)。グラフの頂点数が二倍になるので最小頂点被覆が$O(2^N)$とかになるため、$|C|$が$N$の半分以上なら最悪計算量はこっちのほうが良さそう)

実装例

クソコード注意報。
二部グラフの最大マッチングはnetworkxを使っていて、内部ではHopcroft–Karp algorithmが使われているので
計算量は$O(|C|^2M\sqrt{N})$とかになりそう(Mは辺の本数)

import networkx as nx


def minimal_vertex_cover(g: nx.Graph) -> list[int]:
    # 頂点が空ときにmaximum_matchingを呼ぶとエラーが出るため
    if g.number_of_nodes() == 0:
        return list()

    color: dict[int, int] = nx.bipartite.color(g)
    top: set[int] = {n for n, c in color.items() if c}
    matching: dict[int, int] = nx.bipartite.maximum_matching(g, top_nodes=top)
    return list(nx.bipartite.to_vertex_cover(g, matching, top_nodes=top))


def get_alcuin_number(G: list[list[int]]) -> int:
    N: int = len(G)

    g: nx.Graph = nx.Graph()
    g.add_nodes_from(range(N))
    g.add_edges_from((i, j) for i, v in enumerate(G) for j in v)

    C: list[int] = minimal_vertex_cover(g)
    I: list[int] = list(set(range(N)) - set(C))
    for i in C:
        for j in C:
            H: nx.Graph = nx.Graph()
            H.add_nodes_from(range(N * 2))
            # G'を作る
            H.add_edges_from((i, j) for i, v in enumerate(G) for j in v)
            # G''を作る
            H.add_edges_from((i + N, j + N) for i, v in enumerate(G) for j in v)
            for u in I:
                H.add_edge(u, u + N)
            # ---Hが完成---

            # 固定した2頂点とその隣接頂点を除く
            for u in G[i]:
                if u in H:
                    H.remove_node(u)
            if i in H:
                H.remove_node(i)
            for u in G[j]:
                if u + N in H:
                    H.remove_node(u + N)
            if j + N in H:
                H.remove_node(j + N)

            hmis: set[int] = set(range(2 * N)) - set(minimal_vertex_cover(H))
            for u in G[i]:
                hmis -= {u}
            for u in G[j]:
                hmis -= {u + N}

            if N - len(C) <= len(hmis):
                return len(C)
    return len(C) + 1

終わり

は

参考

Csorba, P., Hurkens, C. A. J., & Woeginger, G. J. (2012). The Alcuin number of a graph and its connections to the vertex cover number. SIAM Review, 54(1), 141-154. https://doi.org/10.1137/110848840
Seify, A., & Shahmohamad, H. (2014). Some New Results in the Alcuin Number of Graphs. arXiv preprint arXiv:1409.6949. https://doi.org/10.48550/arXiv.1409.6949