最小費用最大流の悪例題

蟻本に掲載されている最小費用流の実装で、$n$ を頂点数として、$O(2^{n/2} n^2 \log n)$ 時間かかる例題です。

対象となるアルゴリズム

Successive Shortest Path (SSP) 系の最小費用流のアルゴリズム(蟻本、zkw-algorithm)は指数時間かかります。

zkw-algorithm は SSP の実装の 1 つで、Dijkstra の代わりに SPFA を用い、最短路が複数ある場合にそれらを同時に更新するようにしたものを主に指しているようです (?)

補足

Network Flows: Theory, Algorithms, and Applications では、後者の方法(複数の最短路に対しての更新)を SSP と区別して Primal-Dual algorithm と呼んでいるようです。

生成コード

def mcmf_worst_instance(k):
  inf = 5 * 2 ** k // 4
  print("%d %d" % (2 * k + 2, k * (k + 1) + 1))
  for i in range(k):
    print("%d %d %d %d" % (1, i + 2, [1, 3][i] if i < 2 else 5 << (i - 2), 0))
  print("%d %d %d %d" % (2, k + 2, inf, 0))
  for i in range(k):
    for j in range(k):
      if i == j: continue
      print("%d %d %d %d" % (i + 2, k + j + 2, inf, (1 << max(i, j)) - 1))
  for i in range(k):
    print("%d %d %d %d" % (i + 2 + k, 2 * k + 2, 2 if i < 2 else 5 << (i - 2), 0))

mcmf_worst_instance(17) # |V| = 36
  • 頂点 $1$ から頂点 $n$ に流します。
  • 各辺は $u, v, \mathrm{capacity}, \mathrm{cost}$ の順です。