サブモジュラーフロー

組み合わせ最適化 の理論において、劣モジュラフローは、最小コストフロー問題、マトロイド交差、および重み付き有向グラフにおける最小重み二分法を計算する問題を特殊なケースとして含む、一般的なクラスの最適化問題です。これは元々ジャック・エドモンズとリック・ジャイルズによって定式化され、^{[ 1 ]}多項式時間で解くことができます。^{[ 2 ] [ 3 ] [ 4 ]}

古典的な最小費用フロー問題では、入力はフローネットワークであり、各エッジのフロー量の下限と上限を指定する容量と、各エッジに沿った単位フローあたりのコストが与えられています。目標は、各エッジの容量に従い、各頂点へのフローの総量が流出フローの総量に等しいというキルヒホッフの法則に従い、総コストが最小となるフロー量のシステムを見つけることです。劣モジュラフローでも、グラフの頂点の集合に対する劣モジュラ集合関数が与えられます。キルヒホッフの法則に従う代わりに、すべての頂点集合に対して、超過フロー（集合を流入フローと流出フローの差にマッピングする関数）が劣モジュラ関数によって与えられる値以下であることが要求されます。^{[ 4 ]}