マトロイドの胴回り

数学の一分野であるマトロイド理論では、マトロイドの内周は、その最小回路または従属集合のサイズです。マトロイドの共周は、その双対マトロイドの内周です。マトロイド内周は、グラフの最短サイクル、グラフのエッジ接続、二部グラフのホール集合、集合族の偶数集合、および点集合の一般的な位置の概念を一般化します。計算は困難ですが、マトロイドランクと線形表現のフィールドサイズの両方でパラメーター化されている場合、線形マトロイドの固定パラメーターで扱いやすくなります。

例

「内周」という用語はグラフ理論における内周の使用を一般化したものであって、グラフの最短サイクルの長さを意味する。つまり、グラフィックマトロイドの内周は、その基礎となるグラフの内周と同じである。^[1]

他のクラスのマトロイドの内周も、重要な組み合わせ問題に対応しています。たとえば、共グラフマトロイドの内周（またはグラフィックマトロイドの共周）は、基礎となるグラフのエッジ接続、つまりグラフの最小カットのエッジの数に等しくなります。^[1]横断マトロイドの内周は、二部グラフの最小ホール集合の濃度を示します。これは、二部グラフの片側にある頂点の集合で、グラフ内のマッチングのエンドポイントの集合を形成しません。^[2]

ユークリッド空間内の任意の点の集合は、点の直交座標をマトロイド表現のベクトルとして解釈することにより、実数線型マトロイドを生じます。結果として得られるマトロイドの内周は、基礎となる点の集合が一般的な位置にある場合、空間の次元に 1 を加えた値に等しく、それ以外の場合はそれより小さくなります。実数線型マトロイドの内周は圧縮センシングでも発生し、そこでは同じ概念が行列のスパークと呼ばれます。 ^[3]

バイナリマトロイドの内周は、各集合要素の偶数個のコピーを含む集合族の部分集合である最小偶数集合の濃度を与える。^[2]

計算の複雑さ

バイナリマトロイドの内周を決定することはNP困難である。^[4]

さらに、マトロイドを表す行列によって与えられた線形マトロイドの内周を決定することは、内周またはマトロイドのランクによってパラメータ化された場合はW[1]困難であるが、ランクと基礎となるフィールドのサイズの組み合わせによってパラメータ化された場合は固定パラメータで扱いやすい。^[2]

独立オラクルによって与えられた任意のマトロイドの場合、指数以下の数のマトロイドクエリを使用して内周を見つけることは不可能です。^[5]同様に、任意の $r$ 組の要素の向きを与えるオラクルによって記述される、 $n$ 個の要素を持つランク $r$ の実線形マトロイドの場合、内周を決定するにはオラクルクエリが必要です。 ^[6] $\Omega (n^{r-1})$

ガースオラクル（与えられた要素セットの最小の従属サブセットを報告するオラクル）を使用した計算も検討されている。^[7]

参考文献

^ ab Cho, Jung Jin; Chen, Yong; Ding, Yu (2007)、「連結マトロイドの（共）内周について」、離散応用数学、155 (18): 2456–2470、doi : 10.1016/j.dam.2007.06.015、MR 2365057。
^ abc パノラン、ファハド; ラマヌジャン、MS; サウラブ、サケット (2015)、「線形マトロイドの内周と接続の問題のパラメータ化された複雑さについて」(PDF)、フランク・デーン、イェルク・リュディガー・サック、ウルリケ・ステゲ (編)、アルゴリズムとデータ構造: 第 14 回国際シンポジウム、WADS 2015、ビクトリア、ブリティッシュコロンビア州、カナダ、2015 年 8 月 5 ～ 7 日、議事録、コンピュータサイエンスの講義ノート、第 9214 巻、シュプリンガー、pp. 566 ～ 577、doi :10.1007/978-3-319-21840-3_47、ISBN 978-3-319-21839-7。
^ Donoho, David L. ; Elad, Michael (2003)、「ℓ ¹最小化による一般 (非直交) 辞書の最適スパース表現」、米国科学アカデミー紀要、100 (5): 2197–2202、Bibcode :2003PNAS..100.2197D、doi : 10.1073/pnas.0437847100、PMC 153464、PMID 16576749 。
^ Cho、Chen、Ding (2007) は、これが符号理論における Alexander Vardyの結果の帰結であると指摘しています: Vardy、Alexander (1997)、「コードの最小距離を計算することの難しさ」、IEEE Transactions on Information Theory、43 (6): 1757–1766、doi :10.1109/18.641542、MR 1481035。
^ Jensen, Per M.; Korte, Bernhard (1982)、「マトロイド特性アルゴリズムの複雑性」、SIAM Journal on Computing、11 (1): 184–190、doi :10.1137/0211014、MR 0646772。
^ Erickson, J.; Seidel, R. (1995)、「アフィンおよび球面退化の検出に関するより優れた下限値」、離散および計算幾何学、13 (1): 41–57、doi : 10.1007/BF02574027、MR 1300508。
^ ハウスマン、D.; Korte, B. (1981)、「マトロイドのアルゴリズム対公理的定義」、Oberwolfach での数学的プログラミング (Proc. Conf.、Math. Forschungsinstitut、Oberwolfach、1979)、Mathematical Programming Studies、vol. 14、98–111ページ、土井：10.1007/BFb0120924、ISBN 978-3-642-00805-4、MR 0600125。

[ccd-1] Cho, Jung Jin; Chen, Yong; Ding, Yu (2007)、「連結マトロイドの（共）内周について」、離散応用数学、155 (18): 2456–2470、doi : 10.1016/j.dam.2007.06.015、MR 2365057。

[prs-2] パノラン、ファハド; ラマヌジャン、MS; サウラブ、サケット (2015)、「線形マトロイドの内周と接続の問題のパラメータ化された複雑さについて」(PDF)、フランク・デーン、イェルク・リュディガー・サック、ウルリケ・ステゲ (編)、アルゴリズムとデータ構造: 第 14 回国際シンポジウム、WADS 2015、ビクトリア、ブリティッシュコロンビア州、カナダ、2015 年 8 月 5 ～ 7 日、議事録、コンピュータサイエンスの講義ノート、第 9214 巻、シュプリンガー、pp. 566 ～ 577、doi :10.1007/978-3-319-21840-3_47、ISBN 978-3-319-21839-7。

[3] Donoho, David L. ; Elad, Michael (2003)、「ℓ ¹最小化による一般 (非直交) 辞書の最適スパース表現」、米国科学アカデミー紀要、100 (5): 2197–2202、Bibcode :2003PNAS..100.2197D、doi : 10.1073/pnas.0437847100、PMC 153464、PMID 16576749 。

[4] ^ Cho、Chen、Ding (2007) は、これが符号理論における Alexander Vardyの結果の帰結であると指摘しています: Vardy、Alexander (1997)、「コードの最小距離を計算することの難しさ」、IEEE Transactions on Information Theory、43 (6): 1757–1766、doi :10.1109/18.641542、MR 1481035。

[5] Jensen, Per M.; Korte, Bernhard (1982)、「マトロイド特性アルゴリズムの複雑性」、SIAM Journal on Computing、11 (1): 184–190、doi :10.1137/0211014、MR 0646772。

[6] Erickson, J.; Seidel, R. (1995)、「アフィンおよび球面退化の検出に関するより優れた下限値」、離散および計算幾何学、13 (1): 41–57、doi : 10.1007/BF02574027、MR 1300508。

[7] ハウスマン、D.; Korte, B. (1981)、「マトロイドのアルゴリズム対公理的定義」、Oberwolfach での数学的プログラミング (Proc. Conf.、Math. Forschungsinstitut、Oberwolfach、1979)、Mathematical Programming Studies、vol. 14、98–111ページ、土井：10.1007/BFb0120924、ISBN 978-3-642-00805-4、MR 0600125。