競プロにおいて、「Project Selection」や「2 変数劣モジュラ関数の和の最小化」などと呼ばれるテクニックがあります。いずれも、最小カット問題に帰着して解くことができます。これらは次のような関係にあります。なお、俗に「燃やす埋める」と呼ばれているものは Project Selection と同義だと思ってよいと思います。

本記事では、これらのうち「2 変数劣モジュラ関数の和の最小化」までを解説します。まず、「競プロ典型 90 問 040 - Get More Money（★7）」の解説を通して、Project Selection を解説します。その後、それを一般化した「2 変数劣モジュラ関数の和の最小化」について解説します。

0. 「燃やす埋める」の早見表

最初に、コンテスト中に参照する際の利便性を考慮して、劣モジュラ関数をグラフ表現する方法についての早見表を示します。この表の意味については後述していきます。

コスト	制約条件	グラフ	オフセット
$x_{i} = 0$ のときコスト $F$ 、 $x_{j} = 1$ のときコスト $T$	$F, T \ge 0$	頂点 $s$ から頂点 $i$ へ重み $F$ の辺を張り、頂点 $i$ から頂点 $t$ へ重み $T$ の辺を張る	$0$
$x_{i} = 0$ のときコスト $F$ 、 $x_{j} = 1$ のときコスト $T$	$F \ge T$	頂点 $s$ から頂点 $i$ へ重み $F - T$ の辺を張る	$T$
$x_{i} = 0$ のときコスト $F$ 、 $x_{j} = 1$ のときコスト $T$	$F \le T$	頂点 $i$ から頂点 $t$ へ重み $T - F$ の辺を張る	$F$
$x_{i} = 1$ かつ $x_{j} = 0$ のときコスト $C$	$C \ge 0$	頂点 $i$ から頂点 $j$ へ重み $C$ の辺を張る	$0$
$x_{i} = 1$ かつ $x_{j} = 1$ のとき利得 $P$	$P \ge 0$	頂点 $s$ から頂点 $i$ へ重み $P$ の辺を張り、頂点 $i$ から頂点 $j$ へ重み $P$ の辺を張る	$-P$
$x_{i} = 0$ かつ $x_{j} = 0$ のとき利得 $P$	$P \ge 0$	頂点 $j$ から頂点 $t$ へ重み $P$ の辺を張り、頂点 $i$ から頂点 $j$ へ重み $P$ の辺を張る	$-P$
コストが下の関数 $g(x_{i}, x_{j})$	$B + C \ge A + D$	頂点 $i$ から頂点 $t$ へ重み $B-A$ の辺を張り、頂点 $j$ から頂点 $t$ へ重み $D-B$ の辺を張り、頂点 $i$ から頂点 $j$ へ重み $B+C-A-D$ の辺を張る	$A$
$x_{i_{1}} = x_{i_{2}} = \dots = x_{i_{K}} = 1$ のとき利得 $P$	$P \ge 0$	補助頂点 $y$ を用意して、頂点 $s$ から頂点 $y$ へ重み $P$ の辺を張り、頂点 $y$ から各頂点 $x_{i_{j}}$ へ重み $\infty$ の辺を張る	$-P$
$x_{i_{1}} = x_{i_{2}} = \dots = x_{i_{K}} = 0$ のとき利得 $P$	$P \ge 0$	補助頂点 $y$ を用意して、頂点 $y$ から頂点 $t$ へ重み $P$ の辺を張り、各頂点 $x_{i_{j}}$ から頂点 $y$ へ重み $\infty$ の辺を張る	$-P$

$g(x_{i}, x_{j}) = \left\{ \begin{array}{ll} A & (x_{i} = 0, x_{j} = 0 のとき)\\ B & (x_{i} = 0, x_{j} = 1 のとき)\\ C & (x_{i} = 1, x_{j} = 0 のとき)\\ D & (x_{i} = 1, x_{j} = 1 のとき) \end{array} \right.$

なお、この早見表の機能を一通り揃えたライブラリを公開しています。よかったら使ってみてください。

github.com

1. Project Selection とは

例として、次の「競プロ典型 90 問 040 - Get More Money（★7）」を考えます。

問題概要

$N$ 個の家 $1, 2, \dots, N$ がある。家 $i$ に入るためには $W$ のコストがかかるが、その代わり $A_{i}$ の利得が得られる。また、各家 $i$ に対して、次の $k_{i}$ 個の制約条件が付随している。

家 $i$ に入ることなくして、家 $c_{i, 1}$ に入ることはできない
家 $i$ に入ることなくして、家 $c_{i, 2}$ に入ることはできない
...
家 $i$ に入ることなくして、家 $c_{i, k_{i}}$ に入ることはできない

これらの制約条件を満たしながら、いくつかの家に選んで入る。それらの方法のうち、(総利得) - (総コスト) の考えられる最大値を求めよ。

制約

$2 \le N \le 100$
$c_{i, j} \gt i$

解法：Project Selection で定式化する

今回の問題は「 $N$ 個の選択肢があって、それぞれ選択するかしないかという $2^{N}$ 通りの方法の中から最適なものを選ぶ」という形式となっています。そのような問題のうち、DP ではできそうもない問題となると、Project Selection からの最小カットを疑いたくなります。

ここで、まず Project Selection Problem というフレームワークを紹介します。次のような問題です。

$N$ 個の変数 $x_{0}, x_{1}, \dots, x_{N-1}$ があって、それぞれ 0 または 1 の値を取るとします。以下のようにコストが加算されるとき、その総和を最小化したいとします。

1 変数についてのコスト

$x_{i} = 0$ のとき、コスト $F_{i}$ が加算される
$x_{i} = 1$ のとき、コスト $T_{i}$ が加算される

2 変数についてのコスト

$x_{i} = 1$ かつ $x_{j} = 0$ のとき、コスト $C_{i, j}$ が加算される

この Project Selection のフレームワークが適用できる問題は数多くあります。次のリンクに問題リストを集めています。

drken1215.hatenablog.com

今回の「典型 90 問 040」では、次のように考えられます。まず、変数 $x_{0}, x_{1}, \dots, x_{N-1}$ を次のように定義します

$x_{i} = \left\{ \begin{array}{ll} 1 & (家 i に入るとき)\\ 0 & (家 i に入らないとき) \end{array} \right.$

このとき、最小化したいコストを次のように解釈できます。このコストの最小値を、最後に $-1$ 倍したものが答えです。

1 変数についてのコスト

$x_{i} = 0$ のとき、コスト $W - A_{i}$ が加算される ( $x_{i} = 1$ のときはコスト 0)

2 変数についてのコスト

家 $i$ に配置してある各鍵 $v$ について、 $x_{v} = 1$ かつ $x_{i} = 0$ のとき、コスト $\infty$ が加算される

まさに、先ほどの Project Selection フレームワークが使える形となっています。

2. Project Selection のコストをグラフカットとして表す

それでは、Project Selection のコストをグラフのカットとして表現します。その前に、カットという概念を復習しておきます。グラフの 2 頂点 $s, t$ についてのカットを $s$ - $t$ カットと呼ぶことにします。

$s$ - $t$ カットとは、グラフの各頂点 ( $s, t$ 以外) を「 $s$ 側」と「 $t$ 側」とに分離したものを指します。そして、 $s$ - $t$ カットの値とは、 $s$ 側の頂点から $t$ 側の頂点へと移る辺の重みの総和のことをいいます。その最小値を求める問題が最小カット問題です。

たとえば、次のグラフを考えてみましょう。

このグラフにおいて、

$s$ 側の頂点： $1, 3$
$t$ 側の頂点： $0, 2$

としたときのカットは、下図のようになります。 $s$ 側の頂点を始点とし、 $t$ 側の頂点を終点としているような辺を赤色で示しています。この赤色で示した辺の重みの和が、このカットの値です。

注意点として、「 $s$ 側から $s$ 側への辺」「 $t$ 側から $t$ 側への辺」だけでなく、「 $t$ 側から $s$ 側への辺」もカウントしないことに注意しましょう。

以上を踏まえて、Project Selection のコストを表現するようなグラフを考えます。まず、Project Selection の各変数について、次の表のように考えます。

変数の値	対応する頂点の処遇
$x_{i} = 1$ のとき	頂点 $i$ は $s$ 側
$x_{i} = 0$ のとき	頂点 $i$ は $t$ 側

そして、グラフを作るコツは「1 変数のコスト」と「2 変数のコスト」を分けて考えることだと思います。順に見ていきます。全体を通して、グラフの辺の重みは非負でなければならないことを意識しておきます。

1 変数のコスト

次のコストを表現します。

$x_{i} = 0$ のときに、コスト $F_{i}$ が加算される
$x_{i} = 1$ のときに、コスト $T_{i}$ が加算される

まず、 $F_{i}, T_{i} \ge 0$ である場合には、次のグラフでコストを表現できます。

確かめてみましょう。 $x_{i} = 0$ のときは頂点 $i$ は $t$ 側にあり、 $x_{i} = 1$ のときは頂点 $i$ は $s$ 側にあるので、それぞれのカットは次の図のようになります。確かにこのグラフによって、1 変数のコストを表現できていることが分かります。

そして、実は、1 変数のコストについては、 $F_{i}$ や $T_{i}$ の値が負値でもよいです。その理由は、 $x_{i} = 0$ の場合と $x_{i} = 1$ の場合の双方に同じ値を足し引きしても、最適化の構造は変わらないからです。

具体的には、下図のように考えます。

$F_{i} \ge T_{i}$ である場合は、 $x_{i} = 0$ の場合と $x_{i} = 1$ の場合の双方からコスト $T_{i}$ を引くことで (最後に $T_{i}$ を足すようにします)、

$x_{i} = 0$ のときに、コスト $F_{i} - T_{i}$ が加算される
$x_{i} = 1$ のときには、何も加算されない

という場合に帰着されます。上のグラフは、これを表現しています。 $F_{i} \lt T_{i}$ の場合も同様です。

2 変数のコスト

次のコストを表現します。ただし、 $C_{i, j} \ge 0$ であることが必要です。

$x_{i} = 1$ かつ $x_{j} = 0$ のとき、コスト $C_{i, j}$ が加算される

このコストは、次のグラフで表現できます。非常にシンプルですね！

確かめてみましょう。 $x_{i}$ と $x_{j}$ の値に応じて、カットは次の図のようになります。確かに表現できていることがわかります。

以上で、Project Selection のコストをグラフのカットとして表現できました。さらに、Project Selection コストの和を表現したければ、それに応じたグラフの辺を追加すればよいです。

3. 「競プロ典型 90 問 040」の解答

「競プロ典型 90 問 040」に戻り、解法をまとめます。次のようなコストを表現するグラフを構築して、最小カットを求め、それを -1 倍した値が答えとなります。

1 変数についてのコスト

$x_{i} = 0$ のとき、コスト $W - A_{i}$ が加算される ( $x_{i} = 1$ のときはコスト 0)

2 変数についてのコスト

家 $i$ に配置してある各鍵 $v$ について、 $x_{v} = 1$ かつ $x_{i} = 0$ のとき、コスト $\infty$ が加算される

Dinic 法を用いた場合、計算量は $O(N^{4})$ となります。

コード

Project Selection (を一般化した 2 変数劣モジュラ関数の和の最小化) についてはライブラリ化しました。2 変数劣モジュラ関数の和の最小化については、さらに下で言及します。

#include <bits/stdc++.h>
using namespace std;


// 2-variable submodular optimization
template<class COST> struct TwoVariableSubmodularOpt {
    // edge class
    struct Edge {
        // core members
        int rev, from, to;
        COST cap, icap, flow;
        
        // constructor
        Edge(int r, int f, int t, COST c)
        : rev(r), from(f), to(t), cap(c), icap(c), flow(0) {}
        void reset() { cap = icap, flow = 0; }
        
        // debug
        friend ostream& operator << (ostream& s, const Edge& E) {
            return s << E.from << "->" << E.to << '(' << E.flow << '/' << E.icap << ')';
        }
    };
    
    // constructor
    TwoVariableSubmodularOpt() : N(2), S(0), T(0), OFFSET(0) {}
    TwoVariableSubmodularOpt(int n, COST inf = 0)
    : N(n), S(n), T(n + 1), OFFSET(0), INF(inf), list(n + 2) {}
    void init(int n, COST inf = 0) {
        N = n, S = n, T = n + 1;
        OFFSET = 0, INF = inf;
        list.assign(N + 2, Edge());
        pos.clear();
    }
    friend ostream& operator << (ostream& s, const TwoVariableSubmodularOpt &G) {
        const auto &edges = G.get_edges();
        for (const auto &e : edges) s << e << endl;
        return s;
    }

    // add 1-Variable submodular functioin
    void add_single_cost(int xi, COST false_cost, COST true_cost) {
        assert(0 <= xi && xi < N);
        if (false_cost >= true_cost) {
            OFFSET += true_cost;
            add_edge(S, xi, false_cost - true_cost);
        } else {
            OFFSET += false_cost;
            add_edge(xi, T, true_cost - false_cost);
        }
    }
    
    // add "project selection" constraint (xi = T, xj = F is penalty C)
    void add_psp_penalty(int xi, int xj, COST cost) {
        assert(0 <= xi && xi < N);
        assert(0 <= xj && xj < N);
        assert(cost >= 0);
        add_edge(xi, xj, cost);
    }
    
    // add general 2-variable submodular function
    // (xi, xj) = (F, F): A, (F, T): B
    // (xi, xj) = (T, F): C, (T, T): D
    void add_submodular_function(int xi, int xj, COST A, COST B, COST C, COST D) {
        assert(0 <= xi && xi < N);
        assert(0 <= xj && xj < N);
        assert(B + C >= A + D);  // assure submodular function
        OFFSET += A;
        add_single_cost(xi, 0, D - B);
        add_single_cost(xj, 0, B - A);
        add_psp_penalty(xi, xj, B + C - A - D);
    }
    
    // add all True profit
    void add_all_true_profit(const vector<int> &xs, COST profit) {
        assert(profit >= 0);
        int slack = (int)list.size();
        list.resize(slack + 1);
        OFFSET -= profit;
        add_edge(S, slack, profit);
        for (auto xi : xs) {
            assert(xi >= 0 && xi < N);
            add_edge(slack, xi, INF);
        }
    }
    
    // solve
    COST solve() {
        return dinic() + OFFSET;
    }
    vector<bool> reconstruct() {
        vector<bool> res(N, false), seen(list.size(), false);
        queue<int> que;
        seen[S] = true;
        que.push(S);
        while (!que.empty()) {
            int v = que.front();
            que.pop();
            for (const auto &e : list[v]) {
                if (e.cap && !seen[e.to]) {
                    if (e.to < N) res[e.to] = true;
                    seen[e.to] = true;
                    que.push(e.to);
                }
            }
        }
        return res;
    }
    
private:
    // inner data
    int N, S, T;
    COST OFFSET, INF;
    vector<vector<Edge>> list;
    vector<pair<int,int>> pos;
    
    // add edge
    Edge &get_rev_edge(const Edge &e) {
        if (e.from != e.to) return list[e.to][e.rev];
        else return list[e.to][e.rev + 1];
    }
    Edge &get_edge(int i) {
        return list[pos[i].first][pos[i].second];
    }
    const Edge &get_edge(int i) const {
        return list[pos[i].first][pos[i].second];
    }
    vector<Edge> get_edges() const {
        vector<Edge> edges;
        for (int i = 0; i < (int)pos.size(); ++i) {
            edges.push_back(get_edge(i));
        }
        return edges;
    }
    void add_edge(int from, int to, COST cap) {
        if (!cap) return;
        pos.emplace_back(from, (int)list[from].size());
        list[from].push_back(Edge((int)list[to].size(), from, to, cap));
        list[to].push_back(Edge((int)list[from].size() - 1, to, from, 0));
    }
    
    // Dinic's algorithm
    COST dinic(COST limit_flow) {
        COST current_flow = 0;
        vector<int> level((int)list.size(), -1), iter((int)list.size(), 0);
        
        // Dinic BFS
        auto bfs = [&]() -> void {
            level.assign((int)list.size(), -1);
            level[S] = 0;
            queue<int> que;
            que.push(S);
            while (!que.empty()) {
                int v = que.front();
                que.pop();
                for (const Edge &e : list[v]) {
                    if (level[e.to] < 0 && e.cap > 0) {
                        level[e.to] = level[v] + 1;
                        if (e.to == T) return;
                        que.push(e.to);
                    }
                }
            }
        };
        
        // Dinic DFS
        auto dfs = [&](auto self, int v, COST up_flow) {
            if (v == T) return up_flow;
            COST res_flow = 0;
            for (int &i = iter[v]; i < (int)list[v].size(); ++i) {
                Edge &e = list[v][i], &re = get_rev_edge(e);
                if (level[v] >= level[e.to] || e.cap == 0) continue;
                COST flow = self(self, e.to, min(up_flow - res_flow, e.cap));
                if (flow <= 0) continue;
                res_flow += flow;
                e.cap -= flow, e.flow += flow;
                re.cap += flow, re.flow -= flow;
                if (res_flow == up_flow) break;
            }
            return res_flow;
        };
        
        // flow
        while (current_flow < limit_flow) {
            bfs();
            if (level[T] < 0) break;
            iter.assign((int)iter.size(), 0);
            while (current_flow < limit_flow) {
                COST flow = dfs(dfs, S, limit_flow - current_flow);
                if (!flow) break;
                current_flow += flow;
            }
        }
        return current_flow;
    };
    COST dinic() {
        return dinic(numeric_limits<COST>::max());
    }
};


void Kyopro_Typical_90_040() {
    // 入力
    int N, W;
    cin >> N >> W;
    vector<int> A(N);
    vector<vector<int>> c(N);
    for (int i = 0; i < N; ++i) cin >> A[i];
    for (int i = 0; i < N; ++i) {
        int k;
        cin >> k;
        c[i].resize(k);
        for (int j = 0; j < k; ++j) cin >> c[i][j], --c[i][j];
    }
    
    // 家 i に入らない: F, 家 i に入る: T
    TwoVariableSubmodularOpt<long long> tvs(N);
    for (int i = 0; i < N; ++i) {
        tvs.add_single_cost(i, 0, W - A[i]);
    }
    
    // 家 v in c[i] に入るためには家 i に入る必要がある
    // つまり、v: T, i: F は禁止
    const long long INF = 1LL<<50;
    for (int i = 0; i < N; ++i) {
        for (auto v : c[i]) {
            tvs.add_psp_penalty(v, i, INF);
        }
    }
    cout << -tvs.solve() << endl;
}


int main() {
    Kyopro_Typical_90_040();
}

4. 2 変数劣モジュラ関数の和について

「Project Selection のコスト」は、「2 変数劣モジュラ関数の和」の特殊ケースといえます。

まず、劣モジュラ関数を定義しましょう。有限集合 $V = \{0, 1, \dots, N-1\}$ を考えます。このとき、集合 $V$ の各部分集合 $S$ に対して値を取る関数 $f(S)$ が考えられます ( $V$ 上の集合関数と呼びます)。このとき、 $V$ 上の集合関数 $f$ が劣モジュラ関数であるとは、任意の $S, T \subset V$ に対して

$f(S) + f(T) \ge f(S \cap T) + f(S \cup T)$

が成り立つことをいいます。

なお、集合関数 $f$ は、0 と 1 のみからなる $N$ 次元ベクトルを定義域とする関数ともみなせます。具体的には、集合 $S \subset V$ を、次のように捉え直します。各 $i = 0, 1, \dots, N-1$ に対して、0-1 変数 $x_{i}$ を次のように定義します。

$x_{i} = \left\{ \begin{array}{ll} 1 & (i \in S であるとき)\\ 0 & (そうでないとき) \end{array} \right.$

このとき、集合関数 $f$ は、 $N$ 個の 0-1 変数 $x_{0}, x_{1}, \dots, x_{N-1}$ に対して値をとる関数 $f(x_{0}, x_{1}, \dots, x_{N-1})$ ともみなせます。劣モジュラ関数も集合関数の一種ですので、 $N$ 個の 0-1 変数 $x_{0}, x_{1}, \dots, x_{N-1}$ に対して値をとる関数として捉え直すことができます。本記事では、これ以降、劣モジュラ関数をそのように捉え直します。

2 変数劣モジュラ関数の和とは

今回我々が考えたいのは、劣モジュラ関数の特殊ケースである「2 変数劣モジュラ関数の和」です。一般に、劣モジュラ関数の和は劣モジュラ関数であるため、2 変数劣モジュラ関数の和も劣モジュラ関数です。

$N$ 個の 0-1 変数 $x_{0}, x_{1}, \dots, x_{N-1}$ のうち、2 変数 $x_{i}, x_{j}$ を考えましょう。このとき、2 変数関数 $g(x_{i}, x_{j})$ が劣モジュラであるとは、

$g(1, 0) + g(0, 1) \ge g(0, 0) + g(1, 1)$

が成り立つことを言います。集合で考えると、 $S = \{i\}, T = \{j\}$ のとき $S \cap T = \emptyset, S \cup T = \{i, j\}$ なので、確かに上の式が成り立ちます。 $S, T$ のその他のパターンを確かめることによって、上の不等式が 2 変数関数 $g(x_{i}, x_{j})$ が劣モジュラ関数であるための必要十分条件であることが確かめられます。なお、この式は Monge 性とも深い繋がりがありますね。

さて、「2 変数劣モジュラ関数の和」とは、次の式で表されるものを指します。1 変数関数も含めています。

$N$ 個の変数 $x_{0}, x_{1}, \dots, x_{N-1}$ があって、それぞれ 0 または 1 の値を取るとします。このとき、

$f(x_{0}, x_{1}, \dots, x_{N-1}) = \displaystyle \sum_{i} h(x_{i}) + \sum_{i, j} g(x_{i}, x_{j})$

と表される集合関数 $f$ であって、各関数 $g(x_{i}, x_{j})$ が 2 変数劣モジュラ関数であるものを考えます。

ここまでずっと考えて来た Project Selection も「2 変数劣モジュラ関数の和」です。 Project Selection における

$x_{i} = 1$ かつ $x_{j} = 0$ のとき、コスト $C_{i, j}$ が加算される

というコストに対して、次の関数 $g(x_{i}, x_{j})$ を考えましょう。

$g(x_{i}, x_{j}) = \left\{ \begin{array}{ll} 0 & (x_{i} = 0, x_{j} = 0 のとき)\\ 0 & (x_{i} = 0, x_{j} = 1 のとき)\\ C_{i, j} & (x_{i} = 1, x_{j} = 0 のとき)\\ 0 & (x_{i} = 1, x_{j} = 1 のとき) \end{array} \right.$

これは $g(1, 0) + g(0, 1) \ge g(0, 0) + g(1, 1)$ を満たすため、確かに 2 変数劣モジュラ関数です。

2 変数劣モジュラ関数のグラフ表現

それでは、一般の 2 変数劣モジュラ関数をグラフのカットとして表現してみましょう。2 変数関数 $g(x_{i}, x_{j})$ について、

$A = g(0, 0)$
$B = g(0, 1)$
$C = g(1, 0)$
$D = g(1, 1)$

として、

$B + C - A - D \ge 0$

が成り立つとします。この関数は下図のように「4 個の関数の和」に分解できます。

1 個目の関数は、次の定数値関数です
- $g_{1} = A$
2 個目の関数は、次の 1 変数関数です
- $g_2(x_{j}) = \left\{ \begin{array}{ll} 0 & (x_{j} = 0 のとき)\\ B - A & (x_{j} = 1 のとき) \end{array} \right.$
3 個目の関数は、次の 1 変数関数です
- $g_3(x_{i}) = \left\{ \begin{array}{ll} 0 & (x_{i} = 0 のとき)\\ D - B & (x_{i} = 1 のとき) \end{array} \right.$
4 個目の関数は、次の 2 変数関数です
- $g_4(x_{i}, x_{j}) = \left\{ \begin{array}{ll} 0 & (x_{i} = 0, x_{j} = 0 のとき)\\ 0 & (x_{i} = 0, x_{j} = 1 のとき)\\ B+C-A-D & (x_{i} = 1, x_{j} = 0 のとき)\\ 0 & (x_{i} = 1, x_{j} = 1 のとき) \end{array} \right.$

これらはすべて、Project Selection で解説した方法で、グラフカットとして表現できます。特に 4 個目のものについては、劣モジュラ関数であることから、 $B + C - A - D \ge 0$ であることが保証されているため、Project Selection の制約そのものであることが見て取れます。