頂点被覆（Vertex Cover）問題をPySATのHitmanを使って解く

頂点被覆(Wikipedia)問題はそれだけでグラフ理論の1章になるような大きな問題ですが、ここではPySATのHitmanを使って簡単なものを解くことを目指します。

【問題】以下のグラフのすべての辺に接する最小の頂点の集合を求めよ

PySATのHitmanの基本的な使い方

Wikipediaにもある簡単な問題を使ってHitmanの使い方を見て行きます。開発環境はGoogle Colabで、まずPySATのインストールから行います

!pip install python-sat

プログラムとしては辺の情報をリスト形式で入力してHitmanを呼ぶだけという超簡単なものです。期待通り[2,3,4]という結果が得られました。

import pysat
from pysat.examples.hitman import Hitman

hits = [[1,2],[1,3],[2,3],[2,4],[3,5],[4,5],[4,6]]
print(Hitman(bootstrap_with=hits).get())
# [2,3,4]

頂点の重み情報を加える

応用例として頂点に重み情報を加えてみます。weightsパラメータとして渡すのは各々の頂点の数に対して重みを返すDICT形式で渡します。頂点の数字をそのまま重みとしてみます。すると[2,3,4]の代わりに[1,3,4]となりました。

w = {x:x for x in range(1,6+1)}
print(w)
hits = [[1,2],[1,3],[2,3],[2,4],[3,5],[4,5],[4,6]]
print(Hitman(bootstrap_with=hits, weights=w).get())
# {1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6}
# [1, 3, 4]

2位以下の順位を知りたければ、以下のようにenumerateを使って見ることが出来ます。

with Hitman(bootstrap_with=hits, htype='sorted', weights=w) as hitman:
    for hs in hitman.enumerate():
        print(f"{hs}, cost={sum([w[s] for s in hs])}")
# [1, 3, 4], cost=8
# [2, 3, 4], cost=9
# [1, 2, 4, 5], cost=12
# [1, 2, 5, 6], cost=14
# [2, 3, 5, 6], cost=16

（開発環境：Google Colab）

この考え方はProject Euler, Problem 838: Not Coprimeを解くのに役に立ちます。