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