Sparsity matroid （疎性マトロイド）

[hitonanode]

$(k, l) -$ 疎性マトロイド（無向グラフの辺集合 $E$ の独立性の定義：任意の $\emptyset \neq F \subset E$ について $|F| \le k |V(F)| - l$ が成立）は以下の一般化になっている：

• グラフマトロイド
• Bicircular matroid Bicircular matroid - Wikipedia
• 剛性マトロイド Rigidity matroid - Wikipedia

https://www.kurims.kyoto-u.ac.jp/coss/coss2011/tanigawa-2.pdf https://qoj.ac/problem/6382

[hitonanode]

Pebble Game Algorithms and (k, l)-Sparse Graphs に載っていそう

Matroid oracle - Wikipedia の実装について

頂点側を $k$ 倍に拡張して辺側と 2 部マッチングする

• Circuit-find oracle
  • あらかじめ独立集合 $F \subseteq E$ がセットされる
    • DM 分解しておく
  • $F + x$ に対する circuit-find oracle
    • $x$ の両端点に対応する頂点に $l + 1$ 個の空きが確保できるか確認する
    • Circuit がない -> DM 分解しておけば $O(1)$ ？
    • Circuit がある -> 線形時間？
• 独立性オラクル
  • circuit-find oracle を $| F |$ 回使う？

[hitonanode]

Pebble Game Algorithms and (k, l)-Sparse Graphs

本質的には最大二部マッチングを交互道でやっているやつと同じに見えるが、定数倍が軽く一般化も楽に見えるので実装方針はこれがよさそう？

Finding and Maintaining Rigid Components

データ構造を頑張るやつ component が管理できる？