【C#】最小頂点被覆問題の近似アルゴリズムを実装してみる

はじめに

今回は最小頂点被覆問題の近似アルゴリズムを実装してみたいと思います。

最小頂点被覆問題の詳細は後述しますが、NP困難の問題と知られていて多項式時間で解くことできないことが証明されています。

そういった解くことが難しい問題に関して、以下の3つの手段を検討しながらよりよい解析を行うことが一般的です。

汎用性を諦める：入力を特殊なケースに制限する．たとえば一般グラフの代わりに二部グラフのみを扱うなど
効率性：指数時間だが指数の底が小さいもの，たとえば $O(1.1^n)$ 時間などを求める
最適性を諦める：多項式時間でそれなりによい解を求める

http://www.prefield.com/lecture/2019W-or2/2019_OR2_06.pdf

今回はその中の一番下の最適性を諦める方針で、最小頂点被覆問題の考察を行っていきたいと思います。

最小頂点被覆問題とは

入力：無向グラフG = (V, E)
出力： $\forall u, v \in E , u \in S \vee v \in S$ を満たす要素数最小の部分集合 $S \subseteq V$

近似アルゴリズムの疑似コード

$S := \varnothing$

G の辺 e={u,v}を適当に1本選ぶ

uと v を S に入れる

u,v につながっている辺を G からすべて削除する

G に辺が残っていれば 2 に戻る

https://www.jaist.ac.jp/~uehara/course/2013/i482/pdf/13approx.pdf

実装

public static class MinimumVertexCover
{
    public static HashSet<T> Execute<T>(Graph<T> graph)
    {
        var g = new Graph<T>(graph);
        var vertexCoverSet = new HashSet<T>(graph.VertexCount);

        while (true)
        {
            // gから辺(u, v)を一つ選ぶ
            (T, T)? edge = g.Vertices.Where(v => v.Value.Count > 0).Select(v => ((T,T)?)(v.Key, v.Value[0])).FirstOrDefault();

            // 辺が残っていなければ終わり
            if (edge == null) return vertexCoverSet;

            // uとvをVertexCoverSetに入れる
            vertexCoverSet.Add(edge.Value.Item1);
            vertexCoverSet.Add(edge.Value.Item2);

            // u,vにつながっている辺をGから削除する
            for (int i = g.Vertices[edge.Value.Item1].Count - 1; i >= 0; i--)
                g.DeleteEdge(edge.Value.Item1, g.Vertices[edge.Value.Item1][i]);

            for (int i = g.Vertices[edge.Value.Item2].Count - 1; i >= 0; i--)
                g.DeleteEdge(edge.Value.Item2, g.Vertices[edge.Value.Item2][i]);
        }
    }
}

public class Graph<T>
{
    private Dictionary<T, List<T>> _vertices;
    public IReadOnlyDictionary<T, List<T>> Vertices => _vertices;

    public int VertexCount => _vertices.Count;

    public Type GraphType { get; }

    public Graph(Type type)
    {
        _vertices = new Dictionary<T, List<T>>();
        GraphType = type;
    }

    public Graph(Graph<T> graph)
    {
        _vertices = new Dictionary<T, List<T>>();
        GraphType = graph.GraphType;
        foreach (var vertex in graph.Vertices)
        {
            AddVertex(vertex.Key);
            foreach (var to in vertex.Value)
            {
                AddVertex(to);
                AddEdge(vertex.Key, to);
            }
        }
    }

    public bool AddVertex(T label)
    {
        if (_vertices.ContainsKey(label)) return false;
        _vertices[label] = new List<T>();
        return true;
    }

    public bool AddEdge(T from, T to)
    {
        if (!_vertices.ContainsKey(from) || !_vertices.ContainsKey(to)) return false;

        if (GraphType == Type.Direct)
        {
            _vertices[from].Add(to);
        }
        else
        {
            _vertices[from].Add(to);
            _vertices[to].Add(from);
        }
        return true;
    }

    public bool DeleteEdge(T from, T to)
    {
        if (!_vertices.ContainsKey(from) || !_vertices.ContainsKey(to)) return false;

        if (GraphType == Type.Direct)
        {
            _vertices[from].Remove(to);
        }
        else
        {
            _vertices[from].Remove(to);
            _vertices[to].Remove(from);
        }

        return true;
    }

    public enum Type
    {
        Direct,
        UnDirect,
    }
}

安定のグラフの定義がめちゃくちゃ長くてアレですが、仕組みとしてはかなりシンプルだと思います。

実験

実際に以下のグラフで動作させてみましょう。

static void Main(string[] args)
{
    var graph = new Graph<int>(Graph<int>.Type.UnDirect);

    for (int i = 0; i < 6; i++)
        graph.AddVertex(i);

    graph.AddEdge(0, 1);
    graph.AddEdge(1, 2);
    graph.AddEdge(2, 3);
    graph.AddEdge(3, 4);
    graph.AddEdge(4, 5);
    graph.AddEdge(5, 0);
    graph.AddEdge(0, 4);
    graph.AddEdge(1, 4);
    graph.AddEdge(2, 4);
    graph.AddEdge(2, 5);

    var set = MinimumVertexCover.Execute(graph);

    // 0 1 5 2 4 3
    foreach (var v in set)
        Console.WriteLine(v);
}

実はこの問題の最適解は0, 2, 4なのですが、このアルゴリズムは近似アルゴリズムなので0 1 2 3 4 5と余分な頂点も含めて出力してしまいました。

2倍近傍アルゴリズム

このアルゴリズムは $o(|V| + |E|)$ であり、多項式時間アルゴリズムになります。

ただし最適性を諦めているということで， $\frac{|S|}{|S*|} \leq 2$ までの誤差が生じえます。（今回の実験では最悪のケースだったことがうかがえます）

この証明は以下の通り。

$S := \varnothing$

G の辺 e={u,v}を適当に1本選ぶ

uと v を S に入れる

u,v につながっている辺を G からすべて削除する

G に辺が残っていれば 2 に戻る

ステップ2で選ばれた辺 e の集合を C とおく。
e はステップ4で削除されるため同じ辺が2度選ばれることはない。∴2|C| = |S|。
C は頂点を互いに共有しない辺の集合で、e∈C のそれぞれについて少なくとも一方の端点は S* に入っていなければならない。∴|C|≦|S*|
したがって |S|/|S*|≦2|C|/|C| = 2 である。

https://www.jaist.ac.jp/~uehara/course/2013/i482/pdf/13approx.pdf