Rendszeroptimalizálás, 13. tétel

A k-matroid partíciós probléma, ennek algoritmikus megoldása. A 2-matroid-metszet feladat visszavezetése matroid partíciós problémára.

k-matroid partíciós probléma

• MPP_k*: adott k matroid (M_i=(E,F_i), i=1...k). Kérdés: a matroidok összege a szabadmatroidot adja-e, vagyis E előáll-e E₁∪...∪E_k alakban úgy, hogy E_i∈F_i ∀i-re. Feltehető, hogy az E_i halmazok diszjunktak, ezért hívják a feladatot matroid partíciós problémának.

• Lemma*: MPP_k NP-beli, mert tanú rá egy particionálás, és a tanú lineáris időben ellenőrizhető.
  
• Lemma*: MPP_k coNP-beli, mert tanú rá egy X⊆E halmaz, ami biztosan összefüggő az összegben, azaz ∑r_i(X)<|X|.

Algoritmus

Induljunk ki az ∀i E_i=∅ állapotból. Ekkor E_i∈F_i. Az E_i halmazokat addig bővítjük, amíg az uniójuk E nem lesz, vagy ha nem bővíthető, mutatunk egy X tanút.

A bővítéshez bevezetünk egy n+k pontú irányított segédgráfot, amelynek

• Csúcsai E elemei ∪ {p₁, ..., p_k}. p_i az E_i partíció segédpontja.
• (x→p_i) ∈ E(G), ha x∉E_i és E_i∪{x}∈F_i.
  Az ilyen típusú élek azt jelképezi, hogy az E_i partícióba felvehető x a függetlenség megsértése nélkül.
• (x→y) ∈ E(G), ha ∃i x∉E_i, y∈E_i, E_i∪{x}∉F_i, de E_i∪{x}-{y}∈F_i.
  Az ilyen típusú élek azt jelentik, hogy az E_i partícióban az y elem kicserélhető x-re a függetlenség megsértése nélkül.

1. Megkeressük a legrövidebb irányított utat E-∪E_i-ből {p₁, ..., p_k}-ba.
2. Ha van ilyen út, javítunk az út mentén, azaz végrehajtjuk a cseréket. ∪E_i mérete 1-gyel nő. Azért kell a legrövidebb úton végigmenni, mert különben nem garantált, hogy a cserék során nem sérül a partíciók függetlensége.
3. Különben STOP, nemleges a válasz, és a tanú a E-∪E_i-ből irányított úton elérhető pontok halmaza.

Példa

Az algoritmus futására itt egy részletesen bemutatott példa a jobb érthetőség kedvéért:
https://docs.google.com/document/d/1CbHAHJY4M3cxmBel0cgZ47GIgTOgQ4RJwn_MeOxbais

2-matroid-metszet feladat

Lásd 12.tétel

-- Peti - 2007.01.02.

Javítás: ∑r_i(X)<|E| helyett ∑r_i(X)<|X| !

-- Gabo - 2008.01.04.