共通マトロイド問題

【きょうつうまとろいどもんだい (matroid intersection problem)】

マトロイド $\mathbf {M} ^{+}=(N,{\mathcal {I}}^{+})\,$ と $\mathbf {M} ^{-}=(N,{\mathcal {I}}^{-})\,$ における共通独立集合のうちで, 要素数最大のものを求める問題を共通マトロイド問題という. この問題の最適値は, $\mathbf {M} ^{+}\,$ の階数関数 $\rho ^{+}\,$ と $\mathbf {M} ^{-}\,$ の階数関数 $\rho ^{-}\,$ とを用いたエドモンズ(J. Edmonds)の最大最小定理

${\begin{array}{l}\max\{|I|\mid I\in {\mathcal {I}}^{+}\cap {\mathcal {I}}^{-}\}=\\\ \ \ \min\{\rho ^{+}(X)+\rho ^{-}(N\backslash X)\mid X\subseteq N\}\end{array}}\,$

によって特徴付けられる.