Az irányított összefüggőség növelése

Diplomamunka

Készítette: Végh László

Témavezető: Frank András egyetemi tanár

Eötvös Loránd Tudományegyetem Természettudományi Kar

Tartalomjegyzék

1. Előszó 3

2. Bevezetés 5 2.1. Jelölések . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 2.2. Menger-tételek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6 2.3. Dilworth-tételek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8

3. A Szupermoduláris Fedési Tétel 10 3.1. A tétel és bizonyítása . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 3.2. Alkalmazások . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

3.2.1. Halmazfüggvények - Irányított élösszefüggőség növelése . . . . . . . 13 3.2.2. Irányított pontösszefüggőség növelése . . . . . . . . . . . . . . . . . 13 3.2.3. Irányított ST-pontösszefüggőség növelése . . . . . . . . . . . . . . . 14 3.2.4. Irányított ST-élösszefüggőség növelése . . . . . . . . . . . . . . . . 14 3.2.5. Győri tétele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

4. Algoritmusok 18

4.1. k-élösszefüggővé növelés . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

4.1.1. Az algoritmus leírása . . . . . . . . . . . . . . . . . . . . . . . . . . 20 4.2. 1-ST -élösszefüggővé növelés . . . . . . . . . . . . . . . . . . . . . . . . . . 21 4.3. Útgenerálási algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

4.3.1. A súlyozott eset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 4.4. 0-1 értékű szupermoduláris függvény fedése . . . . . . . . . . . . . . . . . . 30

4.4.1. Összefüggőség növelése eggyel . . . . . . . . . . . . . . . . . . . . . 31 4.4.2. Az általános eset . . . . . . . . . . . . . . . . . . . . . . . . . . . . 35

4.5. k-összefüggővé növelés fix k esetén . . . . . . . . . . . . . . . . . . . . . . . 38 4.5.1. Az optimális megoldások szerkezete . . . . . . . . . . . . . . . . . . 38 4.5.2. Ki- és be-hiányok . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 4.5.3. Az algoritmus leírása . . . . . . . . . . . . . . . . . . . . . . . . . . 41

4.6. Approximációs algoritmusok . . . . . . . . . . . . . . . . . . . . . . . . . . 42 4.6.1. Az algoritmus leírása . . . . . . . . . . . . . . . . . . . . . . . . . . 43

5. Keresztezőn szupermoduláris függvények fedési algoritmusa 44

5.1. Alapfogalmak . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44 5.1.1. Erős posetek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5.1.2. Szoros elemek . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46 5.2. 0-1 értékű p fedése . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

5.2.1. A helyesség bizonyítása . . . . . . . . . . . . . . . . . . . . . . . . . 48 5.3. Az általános eset . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51

5.3.1. Pushdown-Reduce az általános esetben . . . . . . . . . . . . . . 52 5.3.2. A PushToMin szubrutin . . . . . . . . . . . . . . . . . . . . . . . 55

5.4. Megvalósítás gráfokon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 5.4.1. Bonyolultság . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

1. fejezet

Előszó

Dolgozatunkban az irányított gráf összefüggőség-növelésének kérdését fogjuk tárgyalni, elsősorban algoritmikus szempontból. A k-szoros összefüggőség az összefüggőség fogalmának természetes általánosítása: azt fejezi ki, hogy a gráffal modellezett hálózatunk mennyire biztonságos. k-szorosan összefüggő gráfból tetszőleges k-nál kevesebb csúcs (vagy él) kitörlése után is megmarad az összefüggőség. Azt, hogy egy gráf k-szorosan él- vagy pontösszefüggő-e, a Menger tétel segítségével egyszerűen el tudjuk dönteni.

Alapkérdésünk a következő lesz: adott egy irányított gráf és egy k szám. Tegyük e gráfot a lehető legkevesebb új él behúzásával k-szorosan él- vagy pontösszefüggővé.

Az élösszefüggőség növelésének kérdését az irányított esetben Frank András oldotta meg Mader leemelési tételének segítségével [4]. Ennél jóval bonyolultabbnak bizonyult a pontösszefüggőség növelése, sőt, már az ST -élösszefüggőség növelése is. Irányított pontösszefüggőséggel kapcsolatban az első eredmény k = 1 esetére született, Eswaran és Tarjan munkájaként [6]. E téren Frank András és Jordán Tibor 1995-ös minimax-formulája jelentett áttörést [1]. Ebben halmazpárokon értelmezett keresztezőn szupermoduláris függvények fedéseként fogalmazták meg mind az él-, mind a pontösszefüggőség növelésének feladatát, valamint ezek általánosabb, ST -összefüggőségi változatait is. Ez az általános keret magában foglalja Győri útrendszerek generálásáról szóló tételét is [7], mely addig semmilyen más minimax-tétellel nem mutatott rokonságot. E tételre a továbbiakban Szupermoduláris Fedési Tétel néven hivatkozunk. Az optimum megtalálására [1] csupán ellipszoid módszert használó algoritmust adott, ezért a következő kutatások fő célja kombinatorikus algoritmus keresése lett.

Az első egyszerű gráfalgoritmus Steffen Ennitől származik [13], amely azonban csak 1-ST -összefüggővé növelésre használható. Az általános problémához kötődő első eredmény Jordán Tibor approximációs algoritmusa, mely tetszőleges digráfra legfeljebb k − 1-gyel több élt ad meg az optimálisnál [14]. A pontos optimum kiszámítását rögzített k esetén Frank András és Jordán Tibor oldja meg algoritmikusan [3], ennek hátránya, hogy futásideje k-ban exponenciális.

Frank András egyszerű algoritmust adott az útgenerálási probléma megoldására [8], melyet később sikerült kiterjesztenie a Szupermoduláris Fedési Tétel azon esetére, amikor szupermoduláris függvényünk csak 0 és 1 értéket vehet fel [11]. Ennek legfontosabb alkalmazása a k − 1-összefüggő digráf k-összefüggővé növelése lehetne, azonban erre az algoritmus közvetlenül nem volt használható.

Más irányból közelítette meg a 0-1 értékű esetet ifj. Benczúr András [12], aki a tételt alkalmas posetekre fogalmazta át. Ezen átfogalmazásra adott egy meglehetősen bonyolult algoritmust, mely alkalmazható mind az összefüggőség, mind az ST -összefüggőség eggyel való növelésének problémájára.

A dolgozat egyik célja, hogy a fenti eredményeket egységes keretben tárgyalja. Másik célunk két új algoritmus bemutatása. Ezen polinomiális idejű algoritmusok egyben alternatív bizonyítást is adnak a szóbanforgó tételekre. Ezek közül az egyik a 4.4 részben szerepel: itt megadjuk a [11] algoritmusnak egy olyan javítását, ami közvetlenül alkalmas az összefüggőség és az ST -összefüggőség eggyel való növelésére. A másikat az 5. fejezetben mutatjuk be: ez egy általános kombinatorikus algoritmus a Szupermoduláris Fedési Tételben szereplő optimum megtalálására. Ez a [12] algoritmus általánosítása, és alkalmazható az irányított összefüggőség-növelés minden fentebb felsorolt esetének megoldására. Az előbbi saját, az utóbbi ifj. Benczúr Andrással közös eredmény.

Köszönetnyilvánítás

Köszönet illeti mindenekelőtt témavezetőmet, Frank Andrást, a téma legjelesebb szakértőjét, aki bevezetett az összefüggőség-növelés problémakörébe, és felbecsülhetetlen segítséget nyújtott munkámhoz. Szeretném megköszönni ifj. Benczúr Andrásnak, hogy kitartóan együttműködött velem közös algoritmusunk elkészítésében. Hálás vagyok Bernáth Attilának és Szabó Jácintnak, akik önzetlenül segítettek az új eredményeket tartalmazó részek alapos átnézésével.

Bevezetés

2.1. Jelölések

Legyen D = (V, A) irányított gráf. A gráf pontjait kisbetűkkel fogjuk jelölni. X, Y, Z általában halmazpárokat fog jelenteni, V részhalmazait más nagybetűk (pl. H, F) jelölik. Ha az e él kezdőpontja x, végpontja pedig y, akkor az e = xy jelölést használjuk, x-et az él tövének, y-t pedig a fejének nevezzük. H ⊆ V és x ∈ V esetén H ∪ {x} helyett gyakran a H + x írásmódot használjuk. n általában a gráf pontszámát, |V |-t fogja jelölni, m pedig az élek számát, |A|-t.

Adott H, F ⊆ V halmazokra jelölje ρ(H, F) a H − F -ből F − H-ba menő élek számát, δ(H, F) pedig az F − H-ból H − F -be menőkét. Legyen ρ(H) = ρ(H, V − H) a H-ba belépő élek száma, δ(H) = δ(H, V − H) a H-ból kilépő élek száma. Mind irányított, mind irányítatlan gráfban legyen d(H, F) az H − F és H − F közti élek száma, d̄(H, F) pedig a H ∩ F és V − H − F közti élek száma (irányított esetben mindegy, hogy melyik irányban). Nevezzük H-t xȳ halmaznak, ha x ∈ V és y ∉ V. Jelölje egy H ⊆ V halmazra Γ^{+}(H) azon x ∈ V − H pontok halmazát, amelyekbe megy él H-beli pontból. Γ^{−}(H) pedig legyen azon V − H-beli pontok halmaza, amelyekből megy él H-ba.

Valamely x, y ∈ V pontokra legyen λ(x, y, D) az x-ből y-ba menő páronként éldiszjunkt irányított utak maximális száma, κ(x, y, D) pedig a páronként belsőleg pontdiszjunktaké. Nyilvánvaló, hogy λ(x, y, D) ≥ κ(x, y, D).

Ha λ(x, y, D) ≥ k, akkor mondjuk azt, hogy D x és y között lokálisan k-élösszefüggő, κ(x, y, D) ≥ k esetén pedig azt, hogy D x és y között lokálisan k-pontösszefüggő.

Ha bármely x, y ∈ V párra λ(x, y, D) ≥ k (illetve κ(x, y, D) ≥ k), akkor mondjuk azt, hogy D k-él/pontösszefüggő. Világos, hogy az 1-él- és az 1-pontösszefüggőség is ekvivalens az erősen összefüggőséggel.

Hasonlóan, ha adott ∅ ≠ S, T ⊂ V halmazokra minden x ∈ S, y ∈ T esetén λ(x, y, D) ≥ k (illetve κ(x, y, D) ≥ k), akkor e gráfot k-szorosan ST -él/pontösszefüggőnek nevezzük. Egy D = (V, A) digráfot egy ∅ ≠ U ⊆ V halmazra U-ban k-él/pontösszefüggőnek hívunk, ha k-szorosan UU-él/pontösszefüggő.

Irányítatlan gráfra ugyanígy definiálhatjuk az él- és pontösszefüggőséget.

Ha nem mondjuk, hogy milyen összefüggőségről van szó, az minden esetben pontösszefüggőség lesz. Feltételezzük a Maximális Folyam-Minimális Vágás tétel és a hozzá tartozó O(n^{3}) idejű algoritmus (MFMC) ismeretét. Ez például [20]-ben található meg.

2.2. Menger-tételek

Mind az irányított, mind az irányítatlan esetben a Menger-tételek jó karakterizációját adják annak, hogy mikor lokálisan k-él/pontösszefüggő egy gráf két adott pont között. A tételt az MFMC tételre vezetjük vissza. A bizonyítás ezért hatékony algoritmust is fog adni mind az él-, mind a pontösszefüggőség kérdésének eldöntésére.

2.2.1. Tétel (Menger). Legyen D = (V, A) irányított gráf, k pozitív egész, x, y ∈ D.

(i) D akkor és csak akkor lokálisan k-élösszefüggő x és y között, ha tetszőleges k-nál kevesebb élt elhagyva még marad x és y közt irányított út.

(ii) D akkor és csak akkor lokálisan k-pontösszefüggő x és y között, ha |V | ≥ k + 1, és bármely k-nál kevesebb, x-től és y-tól különböző pontot kihagyva marad x és y közt irányított út.

(iii) Analóg állítások érvényesek az irányítatlan esetben is.

Az (i) és (ii) állítások alábbi közös általánosítását látjuk be. Az (i) állítás az r = 1, l = k speciális esetben fog adódni, a (ii) állítás pedig az r = k, l = 1 esetből fog könnyen következni.

2.2.2. Tétel. Legyen D = (V, A) digráf és r, l pozitív egészek, x, y ∈ D. Akkor és csak akkor létezik x-ből y-ba rl élidegen út, hogy bármely csúcson legfeljebb l út megy át, ha bárhogy kihagyva egy H ∈ V − {x, y} halmazt (0 ≤ |H| ≤ r − 1), a maradékban minden xȳ halmazból legalább (r − |H|)l él kilép.

Bizonyítás. A feltétel szükséges, hiszen ha létezik egy megfelelő útrendszer, akkor közülük egy adott H halmazból legfeljebb l|H| használhat pontot. A maradék (r − |H|)l út ezért D − H-ban halad, ami miatt D − H-ban minden xȳ halmazból valóban legalább (r − |H|)l él lép ki.

Az elegendőség igazolásához először is elhagyhatjuk az x-be belépő és az y-ból kilépő éleket. Készítsük el azt a D′ = (V′, A′) gráfot, amiben minden v ∈ V pontnak megfelel egy v′ és egy v′′ pont. Az éleket pedig húzzuk be úgy, hogy ha uv ∈ A, akkor legyen u′′v′ ∈ A′. Legyen továbbá minden v ∈ V -re v′v′′ ∈ A′. Ebben a hálózatban legyen a g kapacitásfüggvény értéke l a v′v′′ éleken, a többi élen pedig 1. A feltétel éppen azt mondja ki, hogy D′-ben minden S′ ⊆ V′ x′′ȳ′ halmazra δ′_{g}(S′) ≥ rl. Az MFMC tétel szerint ekkor létezik x′′ és y′ közt rl értékű folyam. Ez felbomlik körfolyamokra és rl útfolyamra. Ezen rl útfolyamnak az eredeti gráfban kl élidegen út felel meg, úgy, hogy bármely csúcson legfeljebb l halad keresztül. □

2.2.1 (iii) Bizonyítása. Az irányítatlan esetet visszavezetjük az irányítottra. Legyen G = (V, E) az irányítatlan gráfunk, és készítsük el azt a D = (V, A) digráfot, amelyben minden uv ∈ E élt egy uv, vu ∈ A élpár helyettesít. Világos, hogy ha G-ben van k él/pontdiszjunkt út x és y között, akkor D-ben is lesz k él/pontdiszjunkt irányított út. Megfordítva, ha Dben adott k darab belsőleg pontdiszjunkt út x és y közt, akkor az G-ben is k belsőleg pontdiszjunkt útnak felel meg. Tegyük most fel, hogy D-ben létezik k éldiszjunkt út x és y között. Válasszuk ezeket úgy, hogy összesen minimális számú élt használjanak. Csak abból lehet baj, ha van olyan L_{1} és L_{2} út, valamint uv, vu ∈ A élpár, hogy uv ∈ L_{1}, vu ∈ L_{2}. Ekkor viszont L_{1} és L_{2} könnyen helyettesíthetők olyan útpárral, hogy élhalmazaik uniója L_{1} ∪ L_{2} − {uv, vu}. Ez azonban ellentmond az útrendszer minimális választásának.

Könnyen belátható továbbá, hogy az (i) és (ii) pontok feltételei a k-szoros irányított él/pontösszefüggőségre D-ben ekvivalensek az irányítatlan esetben kimondható analóg feltételekkel G-ben. □

A Menger tétel triviális következménye, hogy egy D = (V, A) irányított gráf pontosan akkor k-élösszefüggő, ha bármely ∅ ≠ H ⊂ V halmazra δ(H) ≥ k. Ugyanígy adható feltétel az ST -élösszefüggőségre. Nevezzünk egy H halmazt ST -halmaznak, ha S ∩ H ≠ ∅, T − H ≠ ∅.

2.2.3. Lemma. Egy D = (V, A) irányított gráf pontosan akkor k-szorosan ST -élösszefüggő valamely ∅ ≠ S, T ⊆ V halmazokra, ha minden H ST -halmazra δ(H) ≥ k.

A k-pontösszefüggőség jellemzéséhez halmazpárokra lesz szükségünk. Tegyük fel, hogy k + 1 ≤ |V |. V diszjunkt nemüres részhalmazaiból álló X = (X^{−}, X^{+}) párra legyen h(X^{−}, X^{+}) := |V − (X^{−} ∪ X^{+})|. Azt mondjuk, hogy X egyirányú pár (D-re nézve), ha nem megy él X^{−}-ból X^{+}-ba.

2.2.4. Lemma. A D = (V, A) irányított gráf pontosan akkor k-összefüggő, ha

h(X^{−}, X^{+}) ≥ k  (2.1)

minden X egyirányú párra.

Bizonyítás. A szükségességhez azt kell látni, hogy ha D k összefüggő, akkor egy x ∈ X^{−} pontból létezik k darab belsőleg pontdiszjunkt út egy y ∈ X^{+} pontba. Mivel X egyirányú, ezért ezek mindegyike tartalmaz pontot V − (X^{−} ∪ X^{+})-ban.

Tegyük fel, hogy fennáll a feltétel, mégis egy x ∈ V pontból nincs k darab pontdiszjunkt út egy y ∈ V pontba. Amennyiben nincsen xy él, úgy a Menger tétel szerint van egy C ⊆ V − {x, y} halmaz, amire |C| < k, és C lefogja az összes x-ből y-ba menő irányított utat. Legyen X^{−} a D −C gráfban az x-ből elérhető pontok halmaza, és X^{+} = V −C −X^{−}. Ez az (X^{−}, X^{+}) pár megsérti a feltételt.

Ha pedig létezne α darab x-ből y-ba menő él (α ≥ 1), akkor ugyanez a gondolatmenet D helyett az x-ből y-ba menő élek elhagyásával keletkező D′ gráfban megad egy olyan (X_{0}^{−}, X_{0}^{+}) párt, aki D′-ben egyirányú, és h(X_{0}^{−}, X_{0}^{+}) ≤ k − 1 − α. Ha |X_{0}^{+}| > 1, akkor X^{+} = X_{0}^{+} − y nem üres, (X_{0}^{−}, X^{+}) egyirányú pár D-ben és h(X_{0}^{−}, X^{+}) ≤ k − α. Tehát |X_{0}^{+}| = 1, és hasonlóan |X_{0}^{−}| = 1. Ebből azonban h(X_{0}^{−}, X_{0}^{+}) = |V | − 2 ≥ k − 1, ami ellentmondás. □

Az ST -pontösszefüggőség jellemzéséhez nem elég az egyirányú párokat vizsgálni. Nevezzünk egy diszjunkt nemüres részhalmazokból álló X = (X^{−}, X^{+}) (nem feltétlenül egyirányú!) párt ST -párnak, ha X^{−} ∩ S ≠ ∅, X^{+} ∩ T ≠ ∅. Az alábbi állítás a Menger-tétel 2.2.2 változatából következik egyszerűen.

2.2.5. Lemma. A D = (V, A) irányított gráf adott ∅ ≠ S, T ⊆ V halmazok esetén pontosan akkor k-szorosan ST -összefüggő, ha

δ(X^{−}, X^{+}) + h(X^{−}, X^{+}) ≥ k  (2.2)

minden X ST -párra.

Az k-él és pontösszefüggőség kérdését tehát egy folyamalgoritmus végrehajtásával el tudjuk dönteni.

2.3. Dilworth-tételek

Úgy a Szupermoduláris Fedési Tétel bizonyításában, mint több algoritmusban is szerepet fognak játszani a posetek láncaira és antiláncaira vonatkozó Dilworth tételek és algoritmusok. Legyen (P, ⪯) poset. Láncnak nevezzük P egy páronként összehasonlítható, antiláncnak pedig egy páronként nem összehasonlítható elemekből álló részhalmazát. Legyen adott továbbá egy w : P → Z^{+} súlyozás. Mondjuk azt, hogy egy láncfelbontás (antiláncfelbontás) fedi (P, w)-t, ha minden p_{j} elem legalább w(p_{j}) láncban (antiláncban) szerepel.

2.3.1. Tétel (Súlyozott Poláris Dilworth). A (P, w)-t fedő antiláncok minimális c_{w}(P) száma egyenlő a legsúlyosabb lánc m_{w}(P) súlyával.

Bizonyítás. A max ≤ min irány nyilvánvaló, mivel egy antiláncnak és egy láncnak legfeljebb egy közös eleme lehet. A min ≤ max irányhoz m_{w}(P) szerinti indukciót alkalmazunk. Ha m_{w}(P) = 1, akkor az állítás triviális. m_{w}(P) > 1 esetén legyen A_{1} a P minimális elemeinek halmaza, mely nyilvánvalóan antilánc lesz. Legyen (P′, w′) az a súlyozott poset, melyben minden p_{i} ∈ A_{1}-re w(p_{i}) > 1 esetén w(p_{i})-t eggyel csökkentjük, w(p_{i}) = 1 esetén pedig elhagyjuk a p_{i} elemet. m_{w}(P′) = m_{w}(P) − 1, hiszen P′ minden lánca P -ben eggyel nagyobb súlyú lesz, vagy kiegészíthető egy eggyel hosszabb lánccá. Az indukció szerint P′ felbontható m_{w}(P′) antiláncra, amikhez A_{1}-t hozzávéve P egy m_{w}(P) antiláncból álló felbontását kapjuk. □

Ezen bizonyítás segítségével egyszerű algoritmus adható egy minimális antiláncfedés és leghosszabb súlyú lánc megtalálására, melyek tehát ugyanakkorák lesznek. Legyen A_{1} a P minimális elemeinek halmaza, γ_{1} = min{w(p_{j}) : p_{j} ∈ A_{1}}. P -ben A_{1} minden elemének súlyát csökkentsük γ_{1}-gyel, azon elemeket, akiknek így nullára csökken a súlya, hagyjuk el. Legyen A_{2} a minimális elemek halmaza az így kapott posetben, γ_{2} pedig A_{2} minimális súlyú elemének súlya. Ezt folytatva kapjuk az γ_{1}A_{1}, …, γ_{l}A_{l} antiláncfelbontást. (γ_{i}A_{i} azt jelenti, hogy az A_{i} antilánc γ_{i} példányban szerepel). a_{l} legyen A_{l} tetszőleges eleme. a_{l} nem került bele A_{l−1}-be, kell legyen tehát a_{l−1} ∈ A_{l−1}, a_{l−1} ≺ a_{l} elem. Ő nem került bele A_{l−2}- be, ezért van egy a_{l−2} ∈ A_{l−2}, a_{l−2} ≺ a_{l−1}. Folytassuk ezt az eljárást. Világos, hogy P -ben w(a_{i}) ≥ γ_{i}, tehát egy legalább ∑_{i} γ_{i} súlyú láncot fogunk kapni.

2.3.2. Tétel (Súlyozott Dilworth). A (P, w)-t fedő láncok minimális a_{w}(P) száma egyenlő a legsúlyosabb antilánc d_{w}(P) súlyával.

Bizonyítás. Legyen |P | = n. A nemtriviális min ≤ max irány bizonyítását az MFMC tételre vezetjük vissza. Készítsük el az alábbi D = (V, A) digráfot és g kapacitásfüggvényt: minden p_{i}-nek feleljen meg egy a_{i} és egy b_{i} pont. Legyen ezeken kívül egy s és egy t pont. Minden i-re legyen egy sa_{i} és egy b_{i}t él, g(sa_{i}) = g(b_{i}t) = w(p_{i}) kapacitással, valamint ha p_{i} < p_{j}, akkor egy a_{j}b_{i} él g(a_{j}b_{i}) = ∞ kapacitással. (a_{i}b_{i} ∉ A!).

Az MFMC algoritmus ebben megad egy egészértékű x maximális megengedett folyamot, és egy olyan S st̄halmazt, melyre δ_{g}(S) minimális. Az MFMC tétel szerint δ_{x}(s) = δ_{x}(S) = δ_{g}(S).

V -n megadunk egy másik, D′ = (V, A′) digráfot is, melynek élei minden i-re sa_{i}, b_{i}t és a_{i}b_{i}, valamint p_{i} < p_{j} esetén b_{i}a_{j}. x′ : A′ → Z_{+} legyen az alábbi: Minden i-re legyen x′(sa_{i}) = w(p_{i}) − x(sa_{i}), x′(b_{i}t) = w(p_{i}) − x(b_{i}t), x′(a_{i}b_{i}) = w(p_{i}). p_{i} < p_{j} esetén pedig legyen x′(b_{i}a_{j}) = x(a_{j}b_{i}). Könnyen látható, hogy x′ egy nemnegatív egészértékű folyam lesz, melynek értéke δ_{x′}(s) = w(P) − δ_{x}(s).

Indukcióval látható, hogy egy n′ csúcsú és m′ élű aciklikus digráfban minden folyam felbomlik legfeljebb m′ −n′ +2 útfolyam összegére. D′ egy st útfolyama P -ben egy láncnak felel meg. D′-nek 2n+2 csúcsa van, élszáma legfeljebb 3n+\binom{n}{2}, azaz x′ felbomlik legfeljebb n^{2} útfolyamra. Ez tehát P -ben megad egy γ_{1}C_{1}, …, γ_{l}C_{l} láncfedést (amit ismét úgy értünk, hogy a C_{i} lánc γ_{i} példányban szerepel.) Erre ∑_{i} γ_{i} = δ_{x′}(s) = w(P)−δ_{x}(s) = w(P)−δ_{g}(S) lesz.

Tekintsük most a D-ben meghatározott S minimális vágást.

2.3.3. Állítás. Ha b_{i} ∈ S, akkor a_{i} ∈ S.

Bizonyítás. Tegyük fel indirekten, hogy b_{i} ∈ S, a_{i} ∉ S. Kell legyen olyan k, melyre b_{k} ∉ S és p_{i} > p_{k}, hiszen egyébként δ_{g}(S+a_{i}) < δ_{g}(S) lenne, ellentmondva s választásának. Ugyanígy kell legyen olyan j, hogy a_{j} ∈ S és p_{i} < p_{j}, különben δ_{g}(S − b_{i}) < δ_{g}(S) ellentmondást adna. Ekkor p_{k} < p_{j}, tehát a végtelen kapacitású a_{k}b_{j} él kilép S-ből, azaz δ_{g}(S) = ∞. □

Legyen most A = {p_{i} : a_{i} ∈ S, b_{i} ∉ S}. Világos, hogy A antilánc, és az előbbi állítás miatt miatt w(A) = w(P) − δ_{g}(S) = ∑_{i} γ_{i}, ami a láncfedésünk méretével volt egyenlő. □

A maximális súlyú antiláncot és minimális láncfelbontást találó algoritmus tehát triviálisan visszavezethető az MFMC algoritmusra.

Bonyolultság

A súlyozott poláris Dilworth algoritmus bonyolultsága nagyban függ a poset tulajdonságaitól és reprezentációjától. Tegyük fel, hogy L_{w} felső korlát a maximális láncsúlyra, és az összes minimális elem megtalálása M időben történik. Ekkor az algoritmus egy lépése M időt vesz igénybe, és minden lépésben csökken L_{w} is és |P | is. Tehát a futásidő O(max(L_{w}, |P |)M).

A súlyozott Dilworth-algoritmusban egy 2|P | + 2 pontú hálózaton kell MFMC algoritmust végrehajtani, majd egy folyamot felbontani legfeljebb |P |^{2} útfolyamra. Ennek összideje tehát O(|P |^{3}).

A Szupermoduláris Fedési Tétel

3.1. A tétel és bizonyítása

Az ebben a fejezetben leírt összes eredmény Frank András és Jordán Tibor [1] cikkéből származik. Legyen S és T a V halmaz két nemüres részhalmaza. Jelölje A^{∗} = A(S, T) az S-ből T -be menő irányított élek halmazát, A^{∗} = A(S, T) pedig az olyan X = (X^{−}, X^{+}) párok halmazát, amikre ∅ ≠ X^{−} ⊆ S és ∅ ≠ X^{+} ⊆ T, X^{−} ∩ X^{+} = ∅. X^{−}-t e pár tövének, X^{+}-t pedig a fejének fogjuk nevezni.

Mondjuk azt, hogy egy xy él lefogja vagy lefedi az X párt, ha x ∈ X^{−} és y ∈ X^{+}. Egy z : A^{∗} → R vektorra használni fogjuk az alábbi jelöléseket: legyen z(X) := ∑(z(e) : e ∈ A^{∗}, e lefogja X-et). Ha w : A^{∗} → Z_{+} függvény, e ∈ A^{∗} él, akkor legyen c_{w}(e) := ∑(w(X) : X ∈ A^{∗}, e lefogja X-et).

Ha X = (X^{−}, X^{+}) és Y = (Y^{−}, Y^{+}) párok esetén X^{−} ∩ Y^{−} = ∅, akkor őket tődiszjunktnak, X^{+} ∩ Y^{+} = ∅ esetén pedig fejdiszjunktnak fogjuk nevezni. Ha X és Y tővagy fejdiszjunktak, akkor őket függetlennek nevezzük. Világos, hogy két pár pontosan akkor független, ha nem foghatók le egy éllel.

Vezessük be a párokon az alábbi rendezést: X ⪯ Y jelentse azt, hogy X^{−} ⊆ Y^{−} és X^{+} ⊇ Y^{+}. Ha X ⪯ Y vagy Y ⪯ X, akkor nevezzük őket összehasonlíthatónak.

Ha két pár se nem független, se nem összehasonlítható, akkor keresztezőnek fogjuk őket hívni. Az összehasonlítható és keresztező párokat összefoglalóan függőnek nevezzük.

Egy F ⊆ A^{∗} családot keresztezésmentesnek vagy váznak nevezünk, ha nincsenek benne keresztező párok. Keresztezőnek pedig akkor hívjuk, ha bármely X, Y ∈ F keresztező párokra X ∧ Y = (X^{−} ∩ Y^{−}, X^{+} ∪ Y^{+}) és X ∨ Y = (X^{−} ∪ Y^{−}, X^{+} ∩ Y^{+}) is F-beliek. Világos, hogy A(S, T) keresztező rendszer lesz.

Párok egy F ⊆ A^{∗} rendszerét nevezzük h-függetlennek, ha tetszőleges él legfeljebb h elemét fogja le F-nek. A h = 1 esetben a rendszert egyszerűen függetlennek hívjuk, ez azzal ekvivalens, hogy elemei páronként függetlenek (azaz bármely két elem fej- vagy tődiszjunkt). Általánosabban, legyen w : A^{∗} → Z_{+} függvény. Nevezzük w-t h-függetlennek, ha minden e ∈ A^{∗} élre c_{w}(e) ≤ h.

Legyen p A^{∗}-on értelmezett nemnegatív egészértékű függvény. Nevezzük őt keresztezőn szupermodulárisnak, ha minden X, Y ∈ A^{∗} függő párra amennyiben p(X) > 0, p(Y) > 0, akkor

p(X) + p(Y) ≤ p(X ∨ Y) + p(X ∧ Y)

Fordított irányú egyenlőtlenség esetén keresztezőn szubmoduláris függvénynek nevezzük. Azt mondjuk, hogy a z vektor fedi a p függvényt, ha bármely X ∈ A^{∗} párra z(X) ≤ p(X). Legyen τ(p) a p-t fedő élek minimális száma, azaz

τ(p) = min{z(A^{∗}) : z ≥ 0 egészértékű fedése p-nek}

Legyen ν(p) a maximális p-súlyú páronként független elemekből álló rendszer súlya, azaz

ν(p) = max{p(F) : F független}

Ezen előkészületek után kimondhatjuk az alaptételt:

3.1.1. Tétel (Frank András, Jordán Tibor). Ha p nemnegatív egészértékű keresztezőn szupermoduláris függvény A^{∗}-on, akkor τ(p) = ν(p).

Ennek bizonyítása előtt szükségünk lesz pár jelölésre. Egy e = st ∈ A^{∗} élre legyen b_{e}(X) = 1, ha e fedi X-et és b_{e}(X) = 0 egyébként. Adott z : A^{∗} → R_{+} függvényre legyen Y ∈ A^{∗} esetén b_{z}(Y) = z(Y). Az alábbi állítás első fele triviális, a másik fele pedig az ő egyszerű következménye:

3.1.2. Állítás. Mind b_{e}, mind b_{z} szubmoduláris függvény.

Adott p keresztezőn szupermoduláris függvényre és e ∈ A^{∗} élre legyen p^{e} := (p − b_{e})^{+}. Nevezzük e függvényt p e szerinti redukáltjának. Ez azt jelenti, hogy ha e lefogja az X párt és p(X) > 0, akkor p^{e}(X) = p(X) − 1, minden egyéb esetben p^{e}(X) = p(X). Mivel b_{e} szubmoduláris, p keresztezőn szupermoduláris, így p − b_{e} és könnyen láthatóan (p − b_{e})^{+} is keresztezőn szupermoduláris függvények lesznek.

Legyen w : A^{∗} → Z_{+} függvény. Nevezzük w tartójának és jelöljük S_{w}-vel azon X ∈ A^{∗} párok családját, melyekre w(X) > 0. Azt mondjuk, hogy w vázfüggvény, ha a tartója váz (azaz keresztezésmentes).

3.1.3. Lemma. Legyen w : A^{∗} → Z_{+} függvény. Ekkor létezik olyan w̄ : A^{∗} → Z^{+} vázfüggvény, melyre p(w̄) ≥ p(w) és cw̄(e) ≤ c_{w}(e) minden e ∈ A^{∗} élre.

Bizonyítás. Legyen f : A^{∗} → Z_{+} az alábbi függvény: f(X) = (|X^{−}| − |X^{+}|)^{2}. Egyszerű számolásból adódik az alábbi állítás:

3.1.4. Állítás. Ha X és Y keresztező párok, akkor

f(X) + f(Y) > f(X ∨ Y) + f(X ∧ Y)

Legyen most w̄ az a függvény, mely kielégíti a p(w̄) ≥ p(w), cw̄ ≤ c_{w} feltételt, és erre nézve s(w̄) = ∑(w̄(X)f(X) : X ∈ A^{∗}) maximális. Azt állítjuk, hogy w̄ vázfüggvény. Tegyük fel indirekten, hogy Sw̄ tartalmaz X és Y keresztező párokat. Legyen w′(X ∨ Y) = w̄(X ∨ Y) + 1, w′(X ∧ Y) = w̄(X ∧ Y) + 1, w′(X) = w̄(X) − 1, w′(Y) = w̄(Y) − 1, minden más Z ∈ A^{∗} párra pedig w′(Z) = w̄(Z). 3.1.2 miatt c_{w′}(e) ≤ cw̄(e) minden e ∈ A^{∗}- ra, p szupermodularitása miatt pedig p(w′) ≥ p(w̄). A 3.1.4 állítás értelmében viszont s(w′) > s(w̄), ami ellentmond w̄ választásának. □

3.1.1 Bizonyítása. A ν(p) ≤ τ(p) irány triviális: egy F független rendszernek egy él legfeljebb egy elemét foghatja le. Tehát tetszőleges z-re és F-re

z(A^{∗}) ≥ ∑(z(X) : X ∈ F) ≥ ∑(p(X) : X ∈ F) = p(F)

Nézzük most a τ(p) ≤ ν(p) irányt. Tetszőleges e ∈ A^{∗} élre tekintsük p e szerinti redukáltját. p^{e} ≤ p, és - mivel e legfeljebb egy élt foghat le egy független rendszerből - ν(p) − 1 ≤ ν(p_{e}) ≤ ν(p). Nevezzük az e élt csökkentőnek, ha ν(p_{e}) < ν(p). A bizonyítás lényege az alábbi lemma lesz: 3.1.5. Lemma. Ha egy Z párra p(Z) > 0, akkor van Z-t fedő csökkentő él.

Bizonyítás. Tegyük fel indirekten, hogy minden Z-t fedő e élre van egy F_{e} független rendszer, amire p(F_{e}) = ν(p) és e nem fedi F_{e} egyetlen elemét sem. Legyen w_{e} : A^{∗} → {0, 1} olyan függvény, mely 1-et vesz fel F_{e} elemein, azon kívül pedig 0-t. w_{0} pedig legyen olyan, ami egyedül Z-n vesz fel 1-et, mindenhol máshol 0-t. Legyen w := w_{0} + ∑(w_{e} : e fedi Z-t). Legyen h = |Z^{−}||Z^{+}| a Z-t fedő élek száma. Ekkor p(w) = ν_{p}h + p(Z) és így igaz az alábbi két tulajdonság:

p(w) ≥ ν_{p}h + 1  (3.1)
w h-független  (3.2)

A 3.1.3 lemma miatt van olyan w̄ vázfüggvény, mely kielégíti e feltételeket. Legyen I = Sw̄. Ekkor I váz lesz. I-t ⪯ szerint tekintve a váztulajdonság miatt a részbenrendezésben két elem pontosan összehasonlítható, ha mint párok függőek. Ebben egy lánc súlya (3.2) miatt legfeljebb h lehet. Alkalmazzuk a 2.3.1 súlyozott poláris Dilworth-tételt: A maximális láncméret súlya egyenlő a minimális antiláncfelbontás méretével. Van tehát legfeljebb h antiláncunk, akik összesen legalább ν(p)h + 1 súlyú elemet fednek. Ebből következik egy ν(p)-nél nagyobb súlyú antilánc létezése, ami ellentmondás. □

ν(p) ≥ τ(p) bizonyítása ∑(p(X) : X ∈ A^{∗}) szerinti indukcióval fog történni: Ha az összeg 0, akkor ν(p) = τ(p) = 0. Legyen most Z olyan pár, akire p(Z) > 0. Az előző lemma szerint létezik egy Z-t fedő e csökkentő él. Ha z′ p^{e} egy fedése, akkor z′ +e p-nek egy fedése lesz, vagyis τ(p) ≤ τ(p^{e}) + 1. Minthogy ∑ p^{e}(X) < ∑ p(X), alkalmazhatjuk az indukciós feltevést, amiből τ(p) − 1 ≤ τ(p^{e}) = ν(p^{e}) ≤ ν(p^{e}) − 1, ahonnan τ(p) ≤ ν(p) adódik. □

Az alkalmazások során fontos lesz az alábbi definíció: legyenek ∅ ≠ S′ ⊆ S, ∅ ≠ T′ ⊆ T. p_{0}-t, p A(S′, T′)-re való vetítését az alábbi módon definiáljuk: X_{0} ∈ A(S′, T′) esetén legyen

p_{0}(X_{0}) := max(p(X) : X ∈ A(S, T), X^{−} ∩ S = X_{0}^{−}, X^{+} ∩ T = X_{0}^{+})

Könnyen ellenőrizhető, hogy p_{0} is keresztezőn szupermoduláris függvény lesz.

Kimondjuk továbbá e tételt külön abban a speciális esetben, amikor p csak 0-1 értéket vehet fel. Legyen L azon párok rendszere, melyekre p(X) = 1. p keresztező szupermodularitása miatt ha X, Y ∈ L, akkor 2 ≤ p(X ∨ Y) + p(X ∧ Y) ≤ p(X) + p(Y) = 2, amiből az következik, hogy X ∨ Y, X ∧ Y ∈ L. Tehát L keresztező rendszer lesz. Megfordítva, tetszőleges L keresztező rendszerre az a p függvény, ami L elemein egyet, máshol nullát vesz fel, keresztezőn szupermoduláris. A 3.1.1 tétel ebben a speciális esetben így szól:

3.1.6. Tétel. Ha L halmazpárok keresztező rendszere, akkor az L-et lefogó élek minimális τ(L) száma egyenlő lesz az L páronként független elemeinek maximális ν(L) számával.

3.2. Alkalmazások

3.2.1. Halmazfüggvények - Irányított élösszefüggőség növelése

A 3.1.1 tétel jelentősen egyszerűsödik abban a speciális esetben, amikor V = S = T és p csak olyan (X^{−}, X^{+}) párokon lehet pozitív, ahol X^{−} ∪^{∗} X^{+} = V. Ekkor a független rendszerek nagyon speciális alakúak:

3.2.1. Lemma. Legyen I V részhalmazainak olyan rendszere, amelynek bármely két tagja vagy diszjunkt, vagy ko-diszjunkt. Ekkor I tagjai vagy páronként diszjunktak, vagy páronként kodiszjunktak.

Bizonyítás. Tegyük fel, hogy nem igaz az állítás. Ekkor vannak olyan A, B, C ∈ I halmazok, akikre A és B diszjunktak, de A és C ko-diszjunktak. Ekkor azonban B ⊆ C, és ez ellentmondás. □

A 3.1.1 tétel ebben az esetben így szól:

3.2.2. Tétel. Legyen p pozitívan keresztező szupermoduláris függvény V részhalmazain. Ekkor a p-t lefogó élek minimális száma az alábbi maximummal lesz egyenlő:

max{∑_{i=1}^{t} p(V_{i}), ∑_{i=1}^{t} p(V − V_{i}) : V_{1}, …, V_{t} V -nek egy partíciója}

Tegyük fel, hogy adott egy D = (V, A) gráfunk, és szeretnénk őt minimális számú új él hozzávételével k összefüggővé tenni. Legyen az új élek halmaza E. Menger tétele szerint D = (V, A + E) pontosan akkor k-élösszefüggő, ha δ_{D+E}(H) ≥ k minden ∅ ≠ H ⊂ V halmazra. Ez éppen azt jelenti, hogy E-nek le kell fedni a p(H, V − H) = (k − δ(H))^{+} függvényt, mely δ(H) szubmodularitása miatt keresztezőn szupermoduláris lesz. Kimondva az előző tételt ezen esetre:

3.2.3. Tétel. Adott D = (V, A) gráf pontosan akkor tehető legfeljebb γ új él hozzávételével k-élösszefüggővé, ha V -nek minden V_{1}, V_{2}, …, V_{t} részparticiójára

∑_{i=1}^{t}(k − δ(V_{i}))^{+} ≤ γ

∑_{i=1}^{t}(k − ρ(V_{i}))^{+} ≤ γ

3.2.2. Irányított pontösszefüggőség növelése

Legyen D = (V, A) irányított gráf, akit minimális számú új él hozzávételével k-összefüg-gővé szeretnénk tenni (|V | ≥ k + 1). Ha az új élek halmaza E, a 2.2.4 lemma alapján h_{D+E}(X) ≥ k kell fennálljon minden D + E-ben egyirányú párra.

Definiáljuk a p_{def} : A(V, V) → Z_{+} függvényt a következőképpen: p_{def}(X) := (k − h(X))^{+} az egyirányú párokra és 0-nak a többi párra.

Ennek keresztezőn szupermoduláris volta a p_{def} = (k−kδ(X^{−}, X^{+})−h(X^{−}, X^{+}))^{+} felírásból fog következni, mivel mind δ(X^{−}, X^{+}), mind h(X^{−}, X^{+}) szubmoduláris függvények. Könnyen látható, hogy a k-összefüggővé növelés e p_{def} függvény fedésével ekvivalens. A 3.1.1 tétel e speciális esetre kimondva:

3.2.4. Tétel. A D = (V, A) irányított gráf akkor és csak akkor tehető legfeljebb γ él hozzávételével k-összefüggővé, ha minden F független egyirányú párokból álló családra

∑(p_{def}(X) : X ∈ F) ≤ γ

3.2.3. Irányított ST-pontösszefüggőség növelése

Legyenek most a D = (V, A) irányított gráfban adottak az ∅ ≠ S, T ⊆ V halmazok, feladatunk pedig az, hogy minimális számú új él hozzávételével k-szorosan ST -összefüggővé tegyük.

Ha a hozzávett élek halmaza E, a 2.2.5 lemma alapján a D + E gráfban h(X^{−}, X^{+}) ≥ k − δ_{D+E}(X^{−}, X^{+}) kell hogy teljesüljön minden (nem feltétlenül egyirányú) ST -párra.

Legyen (X^{−}, X^{+}) egy diszjunkt halmazokból álló ST -pár, legyen p_{D}(X^{−}, X^{+}) := (k − δ(X^{−}, X^{+}) − h(X^{−}, X^{+}))^{+}. Ennek keresztező szupermodularitása p_{def} esetéhez hasonló módon látható. Feladatunk most ezen függvény fedése.

Mondjuk azt, hogy az X és Y ST -párok ST -függetlenek, ha vagy X^{−} ∩ Y^{−} ∩ S = ∅, vagy X^{+} ∩ Y^{+} ∩ T = ∅. ST -párok egy családját nevezzük ST -függetlennek, ha elemei páronként ST -függetlenek. A 3.1.1 tétel alkalmazásaként az alábbit látjuk be:

3.2.5. Tétel. A D = (V, A) irányított gráf adott ∅ ≠ S, T ⊆ V halmazokra akkor és csak akkor tehető legfeljebb γ S-ből T -be menő él hozzávételével k-szorosan ST -összefüggővé, ha minden F ST -független családra

∑(p_{D}(X) : X ∈ F) ≤ γ  (3.3)

Bizonyítás. A szükségesség abból következik, hogy ha E az új élek halmaza, akkor minden ST -párra δ_{D}(X^{−}, X^{+}) + δ_{E}(X^{−}, X^{+}) ≥ k − h(X^{−}, X^{+}), azaz δ_{E}(X^{−}, X^{+}) ≥ p_{D}(X^{−}, X^{+}) kell teljesüljön. Egy S-ből T -be menő él egy ST -független rendszernek legfeljebb egy elemét tudja lefogni, amiből következik, hogy

γ ≥ |E| ≥ ∑(δ_{E}(X) : X ∈ F) ≥ ∑(p_{D}(X) : X ∈ F)

Az elegendőség igazolásához legyen p_{0} a p_{D} vetítése A(V, V)-ről A(S, T)-re. A (3.3) feltételből következik, hogy minden F_{0} A(S, T)-beli független családra p_{0}(F_{0}) ≤ γ. Innen a 3.1.1 tétel megadja p_{0}-nak egy z : A(S, T) → Z_{+} egészértékű fedését, amire z(A(S, T)) ≤ γ. Álljon E az x ∈ S, y ∈ T pontok közt z(xy) élből. □

3.2.4. Irányított ST-élösszefüggőség növelése

Sajnos általában az ST -élösszefüggőség növelése lényegesen bonyolultabb a (V V -)él-összefüggőség-növelésnél. Itt sem lesz meg az a szerencsénk, hogy a 3.1.1 tétel alkalmazása során a független családok partícióként vagy kopartícióként álljanak elő: az ST - élösszefüggőség növelése nem lesz könnyebb az ST -pontösszefüggőség növelésénél.

Hívjuk a H és F ST -halmazokat ST -függetlennek, ha vagy S ∩ H ∩ F = ∅, vagy H ∪ F ⊇ T. Ez azzal lesz ekvivalens, hogy nincs olyan s ∈ S, t ∈ T pontpár, amelyet mindketten szétválasztanak.

3.2.6. Tétel. A D = (V, A) irányított gráf adott ∅ ≠ S, T ⊆ V halmazokra akkor és csak akkor tehető legfeljebb γ S-ből T -be menő él hozzávételével k-szorosan ST -élösszefüggővé, ha minden F H_{1}, …, H_{t} ST -független halmazrendszerre

∑_{i}(k − δ(H_{i}))^{+} ≤ γ  (3.4)

Bizonyítás. A Menger-tétel szerint D + E pontosan akkor k-szorosan ST -élösszefüggő, ha bármely H ST -halmazra δ_{E}(H) ≥ k − δ_{D}(H). A feltétel szükségessége abból adódik, hogy egy él egy ST -független rendszernek legfeljebb egy elemét képes lefogni.

Az elégségességhez legyen p : A(V, V) → Z_{+} az a függvény, melyre p(X) := (k − δ(X^{−}))^{+} az olyan párokra, amikre ∅ ≠ X^{−} ⊂ V és X^{+} = V − X^{−}, a többi párra pedig p(X) := 0. E függvény keresztező szupermodularitása δ(H) szubmodularitásából adódik. Legyen p_{0} a p_{D} vetítése A(V, V)-ről A(S, T)-re; ez szintén keresztezőn szupermoduláris lesz.

A 3.1.1. tétel alkalmazhatóságához azt kell belátni, hogy ν(p_{0}) ≤ γ. Tegyük fel, hogy ez nem így van: valamely F_{0} A(S, T)-ben független rendszerre p_{0}(F_{0}) > γ. Azon X ∈ F_{0} párokhoz, melyekre p_{0}(X) ≠ 0, legyen v(X) ∈ A(V, V) az a pár, melyre v(X)^{−} ∩ S = X^{−}, v(X)^{+} ∩ T = X^{−} és p_{0}(X) = p(v(X)). Minthogy p(X) > 0, ezért v(X)^{+} = V − v(X)^{−}, p_{0}(X) = p(v(X)) = (k − δ(v(X)^{−}))^{+}. Álljon F az ilyen v(X)^{−} halmazokból. Könnyen látható, hogy F ST-függetlensége ekvivalens F_{0} függetlenségével, ezért F_{0} megsérti a (3.4) feltételt. Ezzel beláttuk, hogy ν(p_{0}) ≤ γ. Ismét tekintsük p_{0}-nak a 3.1.1. tétel által megadott z : A(S, T) → Z_{+} fedését, és álljon E x ∈ S és y ∈ T közt z darab párhuzamos élből. □

A fent leírt esetek mindegyikében a D irányított gráf k-szorosan ST -él/pont összefüggővé tételéhez szükséges élek minimális számát M_{k}(D)-val, a független családok maximális hiányösszegét pedig N_{k}(D)-val fogjuk jelölni. (Az összes esetben M_{k}(D) = N_{k}(D)). Ha egyértelmű, hogy milyen k-ról van szó, akkor az indexet is el fogjuk hagyni.

3.2.5. Győri tétele

Legyen P = (v_{0}, v_{1}, …, v_{n}) egy egyszerű irányított út, és legyen e_{i} = v_{i−1}v_{i}. Legyen adott U = {U_{1}, …, U_{k}}, P részútjainak egy rendszere. Azt mondjuk, hogy P részútjainak egy B rendszere generálja U-t, ha minden U-beli út előáll néhány B-beli út egyesítéseként. Azt szeretnénk vizsgálni, hogy adott U-hoz mennyi a minimális generátorrendszer mérete, γ(U).

Nevezzük az (U, e) párt reprezentált útnak, ahol U egy út és e az ő egy éle. Jelölje (U, e)^{−} az U-nak az e előtti, (U, e)^{+} pedig az e utáni pontjainak halmazát. Jelölje U_{r} az U-beli utakhoz tartozó reprezentált utak halmazát. Egy I út bal végpontját b(I)-vel, jobb végpontját pedig j(I)-vel fogjuk jelölni.

Legyen I = {I_{1}, …, I_{t}} P részútjainak egy családja, és R = {f_{1}, f_{2}, …, f_{t}} egy reprezentáló rendszer: minden i-re f_{i} az I_{i} egy éle. Akkor mondjuk azt, hogy R erős reprezentáló rendszer, ha bármely i, j-re I_{i} ∩ I_{j} f_{i} és f_{j} közül legfeljebb egyet tartalmaz. I-t akkor nevezzük erősen reprezentálhatónak, ha létezik erős reprezentáló rendszere. Egy erősen reprezentálható rendszer generálásához legalább |I| élre van szükség, egy generátorrendszerben kell legyen ugyanis olyan x_{i}y_{i} él, melynek kezdőpontja (I_{i}, f_{i})^{−}-ban, végpontja (I_{i}, f_{i})^{+}-ban van, és ezen éleknek páronként különbözniük kell.

A γ(U)-ra ezért alsó becslést fog adni σ(U), az U-beli legnagyobb erős reprezentálható rendszer mérete. Győri tétele viszont azt mondja ki, hogy ekkora generátorrendszer már létezik is, azaz

3.2.7. Tétel (Győri). Bármely U részút-családra γ(U) = σ(U).

Bizonyítás. A γ ≥ σ irányt az elöbb láttuk. A γ ≤ σ irányhoz először vezessünk be egy fogalmat: az U_{r} egy (U, f) tagját hívjuk soványnak, ha nincs olyan U′ ∈ U, melyre f ∈ U′ ⊂ U. Legyen L_{U} az U_{r}-beli sovány reprezentált utak rendszere.

3.2.8. Lemma. L_{U} keresztező rendszer.

Bizonyítás. Legyen (U, f) és (U′, f′) két keresztező sovány elem, azaz (U, f)^{−}∩(U′, f′)^{−} ≠ ∅, (U, f)^{+} ∩ (U′, f′)^{+} ≠ ∅. (Ez éppen azzal ekvivalens, hogy f, f′ ∈ U ∩ U′.)

Azt állítjuk, hogy (U, f)^{−} és (U′, f′)^{−} nem összehasonlíthatók. Ha például (U, f)^{−} ⊆ (U′, f′)^{−} volna, akkor a soványság és az összefüggőség miatt (U, f)^{+} ⊇ (U′, f′)^{+} adódna. Ekkor azonban (U, f) ⪯ (U′, f′) lenne, ellentmondásban azzal, hogy keresztezők. Hasonlóan feltehető, hogy (U, f)^{+} és (U′, f′)^{+} sem összehasonlíthatók.

A szimmetria miatt feltehetjük, hogy P-n f megelőzi f′-t (vagy esetleg egybeesik vele). A soványság és az előző feltevés miatt ekkor miatt b(U) < b(U′), j(U) < j(U′).

Így az (U, f) ∧ (U′, f′) az (U′, f) reprezentált útnak felel meg, (U, f) ∨ (U′, f′) pedig az (U, f′) reprezentált útnak. Azt kell még belátnunk, hogy (U, f′) és (U′, f) is soványak. A szimmetria miatt ezt elég (U, f′)-re belátni. Ha létezne U-ban olyan Z, akire f′ ∈ Z ⊂ U, akkor (U, f) soványsága miatt f ∉ Z. Ekkor azonban f′ ∈ Z ⊂ U′, ami ellentmond (U′, f) soványságának. □

L_{U} egy független rendszere U egy erősen reprezentálható részének felel meg. Legyen H := {x_{1}y_{1}, …, x_{t}y_{t}} az L_{U} egy minimális fedése. A 3.1.6 tétel szerint |H| = τ(L_{U}) = ν(L_{U}).

3.2.9. Lemma. L_{U} egy H fedése U_{r}-nek is fedése lesz.

Bizonyítás. Tegyük fel, hogy nem így van, és válasszunk egy olyan (U, f) fedetlen párt, akire |U| minimális. (U, f) ∉ L_{U}, mivel L_{U} minden elemét lefogtuk. Ezért van olyan U′, akire f ∈ U′ ⊂ U. |U| minimális választása miatt van olyan él, aki lefogja (U′, f)-t. Ezen él azonban (U, f)-et is lefogja, ami ellentmondás. □

Álljon B azon B_{i} részutakból, melyek első pontja x_{i}, utolsó pontja y_{i}. Az előző lemmából világos, hogy B generálni fogja U-t. Az állítás pedig abból adódik, hogy σ(U) ≥ ν(L_{U}) ≥ τ(L_{U}) ≥ γ(U) □

Bemutatjuk e tétel egy érdekes kombinatorikus geometriai következményét. Legyen T egy derékszögű poligon, azaz a sík függőleges és vízszintes egyenesekkel határolt véges, összefüggő és zárt tartománya. Ez szeretnénk lefedni függőleges és vízszintes oldalú téglalapokkal. (Téglalap alatt a továbbiakban mindig ilyet értünk). Két T -beli pontot akkor nevezünk függetlennek, ha nem fedhetők le egy téglalappal (azaz a kettejük által meghatározott téglalap kilóg T -ből.) A szükséges téglalapok száma alulról becsülhető a páronként független pontok maximális számával. Itt általában nem áll fenn egyenlőség, azonban ha kikötjük T -ről, hogy függőlegesen konvex, azaz minden függőleges egyenest szakaszban metsz, akkor a Győri tételből levezethető az alábbi:

3.2.10. Tétel ([19]). Legyen T függőleges derékszőgű poligon. Ekkor a T -t fedő téglalapok minimális száma egyenlő a páronként független pontok maximális számával.

A Győri tételt kimondhatjuk általánosan is: legyen adott P élein egy w nemnegatív egész értékű súlyfüggvény. Mondjuk azt, hogy P részútjainak egy B halmaza w-generálja U-t, ha minden (U, f) reprezentált útra B legalább w(f) darab f-et tartalmazó részútját tartalmazza U-nak. A minimális generátorrendszer méretét jelölje γ_{w}(U). (A w ≡ 1 eset éppen az útfedési probléma.)

Az (U, f) pár súlya legyen f súlya, azaz w(U, f) = w(f). Legyen a páronként független elemekből álló maximális súlyú rendszer súlya σ_{w}(U). A 3.2.7. tételhez teljesen hasonlóan belátható az alábbi általánosabb alak:

3.2.11. Tétel. Bármely U részút-családra és w nemnegatív egész értékű súlyfüggvényre γ_{w}(U) = σ_{w}(U).

Algoritmusok

4.1. k-élösszefüggővé növelés

Frank András [4] algoritmusa az optimális k-szorosan élösszefüggővé növelésre a Maderféle leemelési tételen fog alapulni. Egy D digráfban az e = zv, f = uz élpár leemelésén az e és f élek elhagyását és az uv él hozzávételét értjük. Az így kapott digráfot D^{ef}-fel fogjuk jelölni. Használni fogjuk az alábbi azonosságokat:

4.1.1. Állítás.

ρ(H) + ρ(F) = ρ(H ∪ F) + ρ(H ∩ F) + d(H, F)  (4.1)
ρ(H) + ρ(F) = ρ(H − F) + ρ(F − H) + d̄(H, F) + ρ(H ∩ F) − δ(H ∩ F)  (4.2)

4.1.2. Tétel (Mader). Legyen a D = (V + s, A) irányított gráf V -ben k-élösszefüggő (k ≥ 1), és tegyük fel, hogy ρ(s) = δ(s). ekkor minden e = st élre létezik olyan f = us él, melyekre az {e, f} leemelésével kapott D^{ef} digráf V -ben k-élösszefüggő.

Bizonyítás. A 2.2.3. lemma szerint az, hogy D V -ben k-élösszefüggő, azzal ekvivalens, hogy

∀ ∅ ≠ H ⊂ V + s halmazra, ha V ∩ H ≠ ∅, V − H ≠ ∅, akkor ρ(H) ≥ k  (4.3)

Egy ∅ ≠ H ⊆ V részhalmazt nevezzünk be-pontosnak, ha ρ(H) = k, és ki-pontosnak, ha δ(H) = k. A ki- vagy be-pontos halmazokat összefoglalóan pontosnak nevezzük.

4.1.3. Lemma. Legyen H és F két t-t tartalmazó pontos halmaz. Ekkor H ∪ F is pontos lesz.

Bizonyítás. Ha H ⊆ F vagy F ⊆ H, akkor készen vagyunk. Az nem lehet, hogy az egyik halmaz ki-pontos, a másik pedig be-pontos, mert ha mondjuk ρ(H) = k, δ(F) = k, akkor F̄ = V − F + s-re 2k = ρ(H) + ρ(F̄) = ρ(H ∪ F̄) + ρ(H ∩ F̄) + d(H, F̄) ≥ 2k + 1, ugyanis d(H, F̄) ≥ 1 az st él miatt.

Tegyük fel, hogy H és F is ki-pontosak (a bizonyítás ugyanaz lesz a be-pontos esetre is). Ha H ∪ F ⊂ V, akkor ρ(H ∪ F) ≥ k teljesül, innen 2k = ρ(H) + ρ(F) ≥ ρ(H ∪ F) + ρ(H ∩ F) ≥ 2k, vagyis készen vagyunk.

Tegyük most fel, hogy H ∪ F = V. Ekkor H̄ ∩ F̄ = {s}, s így a (4.2) egyenlőségben ρ(H̄) + ρ(F̄) = ρ(H̄ − F̄) + ρ(F̄ − H̄) + d̄(H̄, F̄) ≥ 2k + 1, ami ellentmondás. (d̄(H̄, F̄) ≥ 1 szintén az st él miatt van.) □

Ha t nincsen benne egyetlen pontos halmazban sem, akkor e = st-vel bármely f = us él leemelhető. Ha van t-t tartalmazó pontos halmaz, akkor az előző lemma szerint létezik köztük egy egyértelmű M maximális. Nem lehet, hogy minden s-be lépő él M-ből jöjjön: ρ(M) = k esetén δ(V − M) = ρ(M + s) ≤ ρ(M) − 1 = k − 1 állna ellentétben (4.3)-mal, δ(M) = k esetén pedig ρ(V − M) = δ(M + s) ≤ δ(M) − ρ(s) + δ(s) − 1 ≤ k − 1 lenne a probléma. Tehát van olyan f = us él, melyre u ∈ V − M, és ezzel e leemelhető lesz. □

A 3.2.3 tételre fogunk most egy új, algoritmikus bizonyítást adni:

4.1.4. Tétel. Adott D = (V, A) gráf pontosan akkor tehető legfeljebb γ új él hozzávételével k-élösszefüggővé, ha V -nek minden V_{1}, V_{2}, …, V_{t} részpartíciójára

∑_{i=1}^{t}(k − δ(V_{i}))^{+} ≤ γ  (4.4)

∑_{i=1}^{t}(k − ρ(V_{i}))^{+} ≤ γ  (4.5)

Bizonyítás. A szükségesség nyilvánvaló. Az elégségesség bizonyításához képezzük először a D^{o} gráfot D-ből egy új s pont, és V -ből s-be mutató új élek hozzávételével. Az új élek E^{o} halmaza legyen olyan, hogy D^{o} = (V + s, A + E^{o}) teljesítse az alábbi követelményt:

minden ∅ ≠ H ⊂ V halmazra δ_{D^{o}}(H) ≥ k  (4.6)

4.1.5. Lemma. Ha D^{o} = (V + s, A + E^{o}) olyan, hogy E^{o} tartalmazásra nézve minimális, ami eleget tesz a (4.6) feltételnek, akkor |E^{o}| ≤ γ.

Bizonyítás. Jelentse a ki-pontos halmaz itt is az olyan ∅ ≠ H ⊂ V halmazt, melyre δ_{D^{o}}(H) = k. Ez azzal ekvivalens, hogy k − δ_{D}(H) = δ(H, s). Legyen H = {H_{1}, …, H_{t}} maximális ki-pontos halmazok egy családja. Legyen T_{E^{o}} := {v ∈ V : δ(v, s) ≥ 1} az E^{o}-beli élek töveinek halmaza. E^{o} minimalitása miatt ∪_{i}H_{i} le fogja fedni T_{E^{o}}-t.

Tegyük fel, hogy valamely H_{i} és H_{j}-re H_{i} ∪ H_{j} = V. Ekkor a (V − H_{i}, V − H_{j}) részpartícióra (4.5)-t alkalmazva γ ≥ (k − ρ_{D}(V − H_{i})) + (k − ρ_{D}(V − H_{j})) = (k − δ_{D}(H_{i})) + (k − δ_{D}(H_{i})) = δ(H_{i}, s) + δ(H_{j}, s) ≥ δ(V, s) = |E^{o}|, tehát az állítást beláttuk. Az alábbiakban feltesszük, hogy H_{i} ∪ H_{j} ⊂ V minden i, j-re.

Ha H_{i}∩H_{j} ≠ ∅, akkor e feltevés miatt 2k = δ_{D^{o}}(H_{i})+δ_{D^{o}}(H_{j}) ≥ δ_{D^{o}}(H_{i}∪H_{j})+δ_{D^{o}}(H_{i}∩ H_{j}) ≥ 2k, tehát H_{i}∪H_{j} is ki-pontos, ellentmondva H_{i} és H_{j} maximalitásának. Ezért H egy részpartíció. Felírva rá (4.4)-et: γ ≥ ∑_{i}(k − δ_{D}(H_{i})) = ∑_{i} δ(H, s) ≥ δ(T_{E^{o}}, s) = δ(V, s) = |E^{o}|, amiből adódik az állítás. □

Ugyanígy konstruáljuk a D^{i} = (V + s, A ∪ E^{i}) gráfot egy új s pont és s-ből V -be mutató új élek hozzávételével, úgy, hogy az alábbi tulajdonság igaz legyen:

minden ∅ ≠ H ⊂ V halmazra ρ_{D^{i}}(H) ≥ k  (4.7)

Az előzőhöz teljesen hasonlóan látható, hogy ha E^{i} tartalmazásra nézve minimális, akkor |E^{i}| ≤ γ.

Vegyünk most hozzá D-hez egy új s pontot és tartalmazásra nézve minimális E^{o} és E^{i} élhalmazokat. Világos, hogy a D′ = (V + s, A + E^{o} + E^{i}) gráf V -ben k-élösszefüggő lesz. s-re illeszkedő új élek esetleges hozzávételével érjük el, hogy ρ(s) = δ(s) legyen. Az előbbi lemma szerint ez tehető úgy, hogy ρ(s) = δ(s) ≤ γ legyen. A Mader-tétel szerint az s-re illeszkedő éleket párokban leemelhetjük úgy, hogy a gráf V -ben végig k-élösszefüggő maradjon. Ezzel az állítást beláttuk. □

4.1.1. Az algoritmus leírása

Az itt leírt bizonyítás könnyen algoritmussá alakítható.

1. Fázis Vegyünk fel egy új s pontot, és konstruáljunk olyan E^{o} élhalmazt, melyre D^{o} = (V +s, A+E^{o}) kielégíti (4.6)-t és E^{o} tartalmazásra nézve minimális. Ez végrehajtható úgy, hogy minden pontból s-be felveszünk k párhuzamos élt, és közülük mohón addig hagyunk el, csupán (4.6) teljesülésére ügyelve. Azt, hogy egy él elhagyható-e, úgy tudjuk eldönteni, hogy minden x ∈ V pont és s között az MFMC algoritmussal kiszámítjuk a minimális vágás értékét. Hasonlóan konstruáljuk meg E^{i}-t is. Vegyük hozzá D-hez s-et az E^{o} és E^{i} élhalmazokkal. Ha |E^{i}| > |E^{o}| akkor vegyünk fel tetszőleges |E^{i}| − |E^{o}| új s-be menő élt, ha pedig |E^{o}| > |E^{i}|, akkor |E^{o}| − |E^{i}| új s-ből induló élt.

2. Fázis Válasszunk egy e = st élt, és minden u ∈ V -re ellenőrízzük, hogy e és f leemelhetők-e, ahol f az (egyik) u-ból s-be menő él. Ezt szintén MFMC számításokkal láthatjuk. A Mader-tétel szerint kell legyen ilyen f. Emeljük őket le, és az új gráffal kezdjük újra a 2. fázist, egész addig, amíg ρ(s) = δ(s) = 0 nem lesz.

Bonyolultság

Az 1. fázisban E^{o} meghatározása kn él hozzávételével kezdődik, akiket egyenként megvizsgálunk, hogy elhagyjunk-e. Egy él megvizsgálása n − 1 MFMC algoritmussal történik, tehát ennek összbonyolultsága O(kn^{2}MC). Ennyi időbe telik E^{i} meghatározása is. A 2. fázist ρ(s) ≤ kn alkalommal kell megismételni. Egy ismétléskor n−1 u-t kell megvizsgálni, s mindegyikre e és f leemelhetőségének eldöntése 2(n−2) MFMC algoritmussal ellenőrízhető: minden x ∈ V − t − u-ra meg kell vizsgálnunk, hogy ha H egy ux̄ vagy egy xt̄ halmaz, akkor a δ(H) ≥ k feltétel megmarad-e. Tehát a 2. fázis futási ideje O(n^{2}MC). Ezzel az algoritmus futási ideje O(kn^{2}MC).

4.2. 1-ST -élösszefüggővé növelés

Ebben a részben Steffen Enni [13] algoritmusát mutatjuk be az 1-ST -élösszefüggőség növelésére. Ezen algoritmus erősen kihasználja a k = 1 eset tulajdonságait, ezért további esetekre még nem sikerült általánosítani.

Először kimondjuk az 3.2.6 tételt a k = 1 speciális esetre. Egy H ST -halmazt akkor nevezünk pontosnak, ha δ(H) = 0.

4.2.1. Tétel. A D = (V, A) irányított gráf adott ∅ ≠ S, T ⊆ V halmazokra akkor és csak akkor tehető legfeljebb γ S-ből T -be menő él hozzávételével 1-szeresen ST -élösszefüggővé, ha a páronként ST -független pontos ST -halmazok maximális száma legfeljebb γ.

Nevezzük G-t elemi gráfnak, ha G egyszerű irányított páros gráf, melynek osztályai S és T, és G-nek az izolált pontokon kívül háromféle komponense lehet: (1) A komponens ponthalmaza egy s ∈ S és egy t ∈ T pont, melyekre st, ts ∈ A(G) (2) a komponensben minden él S-ből T -be van irányítva (3) a komponensben minden él T -ből S-be van irányítva.

Ha két pont közt mindkét irányba megy él, akkor azt dupla élpárnak hívjuk, ha csak S-ből T -be (vagy T -ből S-be), azt előre (hátra) élnek.

Először elemi gráfokkal fogunk foglalkozni, majd megmutatjuk, hogy miként lehet tetszőleges gráf 1-ST -élösszefüggővé növelését visszavezetni egy elemi gráf 1-ST -élösszefüggővé növelésére.

4.2.2. Lemma. Legyen G = (S ∪ T, A) elemi gráf, és τ azon S-ből T -be menő élek minimális száma, melyek hozzávételével G 1-ST -összefüggővé tehető. Ekkor

1. Ha minden él S-ből T -be mutat, akkor τ = |S||T | − |A|.

2. Ha egyetlen dupla él van és nincsenek hátra élek, akkor τ = |S| + |T | − 2

3. Minden más esetben τ = |S| + |T | − min(|S_{B}|, |T_{B}|), ahol |S_{B}| (illetve |T_{B}|) azon pontok száma S-ben (illetve T -ben), melyekre hátra él illeszkedik.

Bizonyítás. (1): triviális.

(2): Legyen s ∈ S, t ∈ T az a pár, melyek a dupla éllel van összekötve. Minden s ≠ u ∈ S-re legyen C_{u} = u + T − t, és minden t ≠ v ∈ T -re legyen C_{v} = s + T − v. Legyen F = {C_{u} : u ∈ S − s} ∪ {C_{v} : v ∈ T − t}. Ez páronként ST -független szoros ST -halmazokból áll, vagyis τ ≥ |F | = |S| + |T | − 2.

Másrészt, hozzávéve az {sv : v ∈ T − t} ∪ {ut : u ∈ S − s} éleket, 1-ST -összefüggő gráfot fogunk kapni.

(3): Először h := |S| + |T | szerinti indukcióval megadunk egy |S| + |T | − min(|S_{B}|, |T_{B}|) elemű élhalmazt, melyet G-hez véve 1-ST -összefüggő gráfot kapunk. h = 2 esetén G csak egyetlen hátra élből áll, (különben az 1. vagy 2. eset feltétele teljesülne). Ez esetben az él megfordítottjának hozzávétele éppen a szükséges egy elemű növelő halmaz lesz. Ha h > 2, két esetet vizsgálunk:

A. eset Nincsenek sem előre élek, sem dupla élek, és nincsenek izolált pontok: minden pont hátra élekre illeszkedik.

Legyen M = {t_{1}s_{1}, …, t_{n}s_{n}} egy nem bővíthető párosítás (azaz s ∈ S − V (M), t ∈ T − V (M) esetén nincs ts él), és legyenek a kimaradt pontok s_{n+1}, …, s_{n+k}, illetve t_{n+1}, …, t_{n+l}.

Az alábbi éleket vesszük hozzá a gráfhoz: minden 1 ≤ i ≤ n − 1-re vegyük be az s_{i}t_{i+1} élt, valamint az s_{n}t_{1} élt. A fedetlen csúcsokra vegyük be 1 ≤ i ≤ min(k, l)-re az s_{n+i}t_{n+i} éleket. Továbbá ha k > l, akkor minden i > l-re vegyük be az s_{n+i}t_{n+l} élt, ha pedig l > k, akkor minden i > k-ra az s_{n+k}t_{n+i} élt.

Ez összesen n+max(k, l) = max(|S|, |T |) = |S|+|T |−min(|S_{B}|, |T_{B}|) él, mivel S_{B} = S, T_{B} = T. Hozzávételük után minden S-beli pontból minden T -beli pont elérhető lesz. Ez abból következik, hogy az új élek behúzása után az V (M)-beli pontok egy körön helyezkednek el, és - kihasználva azt, hogy az eredeti gráfban nem volt izolált pont és hogy az M nem bővíthető párosítás - minden S − V (M)-beli pontból elérhető M és M-ből elérhető bármely T − V (M)-beli pont. (Enni M-et maximális párosításnak választja, ehelyett azonban elég annyit feltételezni, hogy nem bővíthető.)

B. eset Ha van vagy izolált pont, vagy előre élek által feszített vagy dupla élhez tartozó komponens.

Legyen C = {s_{1}, …, s_{l}, t_{1}, …, t_{k}} ezen komponensek valamelyike. Ha kitöröljük e komponenst, akkor G′ = G−C még mindig kielégíti a 3. eset feltételét, azaz az indukció szerint G′-nek van egy olyan F′ növelése, melyre |F′| = |S′| + |T′| − min(|S′_{B}|, |T′_{B}|) (itt a vesszős mennyiségek G′-ben a megfelelő fogalmak). Világos, hogy S_{B} = S′_{B} és T_{B} = T′_{B}. Legyen ts G′-ben egy él (t ∈ T, s ∈ S). Vegyük hozzá F′-höz az {s_{i}t}_{i=1}^{l} ∪ {st_{j}}_{j=1}^{k} élhalmazt. Ezzel az új élek száma |S′| + |T′| − min(|S′_{B}|, |T′_{B}|) + l + k = |S| + |T | − min(|S_{B}|, |T_{B}|) lesz.

A 3. eset bizonyításához kell még egy |S| + |T | − min(|S_{B}|, |T_{B}|) elemű ST -független pontos ST -halmazt. Csak a |T_{B}| ≥ |S_{B}| esetet vizsgáljuk, a másik esetben hasonló lesz a konstrukció. Legyen S = S_{D} ∪ S_{F} ∪ S_{B}, T = T_{D} ∪ T_{F} ∪ T_{B}, ahol S_{D} (T_{D}) a dupla élekre illeszkedő pontok, S_{F} (T_{F}) pedig az előre élekre illeszkedő vagy izolált pontok. Az alábbiak páronként ST -független pontos ST -halmazok lesznek, éppen a megfelelő számban:

• Minden t_{d} ∈ T_{D}-re legyen s_{d} ∈ S_{D} t_{d} párja, és legyen X = S_{D} − s_{d} + T − t_{d}.

• Minden s_{d} ∈ S_{D}-re legyen t_{d} ∈ T_{D} az s_{d} párja, és legyen X = s_{d} + t_{d} + T_{F} + T_{B}.

• Minden t_{f} ∈ T_{F} -re legyen X = S_{D} + S_{B} + T − t_{f}.

• Minden s_{f} ∈ S_{F} -re legyen X = s_{f} + T_{D} + T_{B}.

• Minden t_{b} ∈ T_{B}-re legyen X = S_{B} + T − t_{b}.

□

Az itt leírt bizonyítás egyben egyszerű algoritmust is ad elemi gráfban a minimális növelő élhalmaz megtalálására. Legyen most adott egy tetszőleges gráf. A következőkben megmutatjuk, hogy minden D digráf elemi gráffá alakítható úgy, hogy a maximális független rendszer mérete, N(D) ne változzék.

0. lépés Úgy módosítjuk a gráfot, hogy S ∩ T = ∅ legyen. Tekintsünk ehhez egy v ∈ S ∩ T pontot. Vegyünk fel egy új v′ pontot, és kössük őt össze dupla éllel v′-vel. T -ből hagyjuk el v-t és vegyük be a helyére v′-t. N(D) ezáltal nem változik, mivel az eredeti gráfban a v-t tartalmazó és az új gráfban a v′-t tartalmazó pontos ST -halmazok kölcsönösen megfeleltethetők egymásnak.

1. lépés Legyen D_{tr} a D tranzitív lezártja. Erre N(D_{tr}) = N(D) nyilvánvaló.

2. lépés Legyen D_{ST} = D_{tr}[S ∪ T], azaz D_{tr} S ∪ T által feszített részgráfja. N(D_{ST}) ≥ N(D_{tr}) abból következik, hogy ha F ST -független D_{tr}-ben, akkor D′ := {X ∩ (S ∪ T) : X ∈ F} ST -független rendszer lesz D_{ST} -ben.

A másik irányú egyenlőtlenséghez legyen F′ D_{ST} -beli ST -független rendszer. Minden X′ ∈ F′-höz legyen X := X′ ∪ {v ∈ V − (S ∪ T) : ∃vx ∈ A(D_{tr}), x ∈ X′}. Kihasználva G_{tr} tranzitív zártságát azt kapjuk, hogy X is pontos ST -halmaz, és az ilyen X-ek páronként ST -függetlenek.

3. lépés Tekintsük D_{ST} olyan erősen összefüggő komponenseit, melyek teljesen S-ben vagy teljesen T -ben helyezkednek el. Húzzuk össze ezeket egy-egy ponttá; legyen az így kapott gráf D′. N(D′) = N(D_{ST}) abból következik, hogy egy 0-kifokú halmaz nem metszhet egy erősen összefüggő komponenst. D′ S illetve T által feszített részgráfjai aciklikusak lesznek; az egyedüli körök egy S-beli és egy T -beli pont közti dupla élek.

4. lépés Képezzük D′-ből H-t úgy, hogy elhagyjuk az olyan s ∈ S csúcsokat, amelyekre van ss′ ∈ A(D′) él, s′ ∈ S, illetve az olyan t ∈ T csúcsokat, melyekre van t′t ∈ A(D′) él, t′ ∈ T. Legyen S_{H} = S ∩ V (H), T_{H} = T ∩ V (H).

N(H) ≤ N(D′) belátásához legyen F egy ST -független rendszer D′-ben, és legyen X ∈ F. Azt állítjuk, hogy X ∩ V (H) S_{H}T_{H}-pontos halmaz lesz H-ban. Ha ezt belátjuk, készen vagyunk, mivel ha X, Y ∈ F ST -függetlenek, akkor X ∩ V (H) és Y ∩ V (H) S_{H}T_{H}- függetlenek lesznek.

X∩V (H) természetesen pontos marad, azt kell csak látni, hogy X∩S_{H} ≠ ∅, T_{H}−X ≠ ∅. Tegyük fel, hogy X ∩ S_{H} = ∅. Legyen s ∈ X ∩ S. Ekkor s ∉ V (H), tehát amiatt, hogy D′ S-re megszorítva tranzitív és aciklikus, ezért kell legyen olyan s′ ∈ S_{H}, melyre ss′ ∈ A(D′). Feltételezésünk szerint s′ ∉ X, vagyis δ(X) ≥ 1, ami ellentmond annak, hogy pontos volt. T_{H} − X ≠ ∅ ugyanígy látható be.

Az N(D′) ≤ N(H) irányhoz legyen F′ egy S_{H}T_{H}-független család H-ban. Minden X′ ∈ F′-höz legyen X := X′ ∪ {t ∈ T : ∃t′ ∈ T_{H} − X′ : t′t ∈ A(D′)}. Álljon F az ilyen X halmazokból. Szintén abból, hogy D′ T -re megszorítva tranzitív és aciklikus, adódik hogy δ(X) = 0, tehát X pontos ST -halmaz. Azt kell belátni, hogy ha X, Y ∈ F, akkor ők ST -függetlenek. Tegyük fel, hogy nem ST -függetlenek, vagyis van s ∈ S ∩ X ∩ Y és t ∈ T − X − Y pontpár.

s ∈ S_{H} következik abból, hogy a definíció szerint X ∩ S, Y ∩ S ⊆ S_{H}. Ha t ∉ S_{H}, akkor kell legyen egy t′ ∈ T_{H} pont, melyre t′t ∈ A(D′). Azt állítjuk, hogy t′ ∈ T_{H} − X′ − Y′. Ellenkező esetben, azaz t′ ∈ X′ ∪ Y′ esetén ugyanis t ∈ X ∪ Y lenne.

Tehát s ∈ S_{H} ∩ X′ ∩ Y′, t′ ∈ T_{H} − X′ − Y′ ellentmondásban X′ és Y′ S_{H}T_{H}- függetlenségével.

4.2.3. Lemma. Tetszőleges D kiindulási digráf esetén a végül kapott H elemi gráf lesz.

Bizonyítás. H mindenesetre páros gráf. Tegyük fel, hogy nem elemi. Ez azzal ekvivalens, hogy van egy t_{1}st_{2} út, t_{1}, t_{2} ∈ T, t_{1} ≠ t_{2}, s ∈ S, vagy pedig van egy s_{1}ts_{2} út, s_{1}, s_{2} ∈ S, s_{1} ≠ s_{2}, t ∈ T. A szimmetria miatt elég az előbbit vizsgálni. Az 1. lépésben a gráfot tranzitívan lezártuk, tehát behúztuk a t_{1}t_{2} élt. A 3. lépésben t_{1}-et és t_{2}-t nem húzhattuk össze. Ekkor azonban a 4. lépés során t_{2}-t törölnünk kellett volna. □

Bonyolultság

A 0-5. lépések megadják az algoritmust, amivel tetszőleges D = (V, A) digráfot H = (S ∪ T, A′) elemi gráffá alakíthatunk. A tranzitív lezárt O(nm) időben megtalálható, az erősen összefüggő komponensek pedig mélységi kereséssel O(n + m) idő alatt. Összesen ez a redukció O(nm) időben elvégezhető. H-ban a növelő élek optimális E_{0} halmaza a 4.2.2. lemma 1. esetében O(|S||T |) = O(n^{2}) időben megtalálható. A 2. esetben O(|S| + |T |) = O(n) idő szükségeltetik, a 3. esetben a tartalmazásra nézve maximális párosítást megtalálni O(m) idő, és a többi lépés O(n) időben végezhető. Összesen tehát az E_{0} megtalálása O(n^{2}) időt vesz igénybe. Ebből egyszerűen előállíthatjuk D egy optimális növelő E élhalmazát: Minden x ∈ V (H)-ra a redukció során jegyezzük meg az x egyik ősét D-ben, legyen ez a(x) ∈ V (D). Egy xy ∈ E_{0} élre legyen a(x)a(y) E-ben egy él. Vagyis az algoritmus futási ideje O(max(n^{2}, nm)).

4.3. Útgenerálási algoritmus

Ebben a fejezetben Győri tételére ismertetjük Frank András algoritmusát, először a súlyozatlan problémára (3.2.7. tétel, [8]), majd a súlyozott esetre (3.2.11. tétel, [9]).

A 3.2.9. lemma és a 3.2.7. bizonyításában leírtaknak megfelelően a sovány reprezentált utak L_{U} rendszerének egy minimális lefogása U egy minimális generátorrendszerének fog megfelelni. Emiatt elég a sovány elemekkel foglalkoznunk. Megadjuk L_{U} egy τ(L_{U}) elemű minimális lefogását és egy ugyanannyi, ν(L_{U}) elemű maximális független részét.

Az algoritmus három fázisban megy végbe. Az első fázisban kiválasztunk L_{U}-ból egy I maximális vázat. A második fázisban a Dilworth-tételt alkalmazzuk: az ismert algoritmussal meghatározzuk I-nak egy K maximális méretű páronként nem összehasonlítható elemekből álló részét és egy minimális láncfelbontását. A váztulajdonság miatt K elemei páronként függetlenek lesznek: ő lesz a duális optimális megoldás. A láncfelbontás I elemeit lefogó F élrendszernek felel meg. A harmadik fázis során F -et alakítjuk úgy át, hogy a mérete nem nő, és végül lefogja L_{U} összes tagját.

1. Fázis A P élein az e_{1}, e_{2}, …, e_{n} sorrendben fogunk végigmenni, úgy, hogy közben L_{U} tagjait két csoportba osztjuk. I lesz a váz, T pedig a tiltott párok csoportja. Kezdetben mindkét csoport üres.

Az i. lépésben tekintsük az összes (I_{1}, e_{i}), (I_{2}, e_{i}), …, (I_{k}, e_{i}) szoros párt. Mivel e párok soványok, így az I_{j} utak élhalmazai nem tartalmazhatják egymást, ezért feltehetjük, hogy b(I_{1}) < ⋯ < b(I_{k}), és j(I_{1}) < ⋯ < j(I_{k}). Mindegyik nem tiltott (I_{j}, e_{i}) szoros párt bevesszük I-be, és letiltjuk az olyan szoros párokat, akiket még nem vizsgáltunk és akik keresztezik őt: azaz az összes olyan (I_{h}, e_{l}) párt, akikre j < h ≤ k, l > i, e_{l} ∈ I_{j}.

Világos, hogy a végül kapott I tartalmazásra nézve maximális váz lesz: minden (I, i) ∉ I párra lesz I-nek egy (I, i)-t keresztező eleme.

2. Fázis A Dilworth algoritmussal meghatározzuk I-nek egy K maximális méretű, páronként független elemekből álló részét és egy minimális láncfelbontásnak megfelelő I-t lefogó F élrendszert. Ezekre |K| = |F | fog teljesülni.

3. Fázis Ha F lefogja L_{U} valamennyi tagját, akkor készen vagyunk. Ha nem ez a helyzet, válasszunk egy olyan (I, i) még nem lefogott párt, melyre |(I, i)^{−}| minimális. (I, i) ∉ I, kell legyen tehát olyan (K, k) ∈ I, melyre k, i ∈ I ∩ J, b(K) < b(I), és k megelőzi i-t. Válasszuk (K, k)-t úgy, hogy (K, k)^{+} minimális legyen.

(I, i)^{−} minimalitása miatt F lefogja (I, k)-t.

4.3.1. Lemma. (K, i) ∈ I.

Bizonyítás. Ha (K, i)-t letiltottuk, úgy kellett legyen olyan (J, e) ∈ I, akire e, i ∈ K ∩ J, b(J) < b(K), és e megelőzi i-t. Ha e megelőzné k-t, akkor (K, k) és (J, e) keresztezők lennének, hiszen k, e ∈ K ∩ J. Tehát e vagy egyenlő k-val, vagy követi. Ekkor (J, e) ∈ I, e, i ∈ I ∩ J, b(J) < b(I) és e megelőzi i-t. Teljesül továbbá (J, e)^{+} ⊂ (K, k)^{+}, ami pedig (K, k)^{+} minimális választásának mond ellent. □

Eszerint F egy f_{1} = x_{1}y_{1} éle lefogja (I, k)-t, egy f_{2} = x_{2}y_{2} éle pedig lefogja (K, i)- t. Legyen f′_{1} = x_{1}y_{2} és f′_{2} = x_{2}y_{1}. Módosítsuk F -et F′-re úgy, hogy az f_{1} és f_{2} éleket kicseréljük f′_{1}-re és f′_{2}-re. Mivel f_{1} és f_{2} nem fogják le (I, i)-t, a szóban forgó pontokról az alábbit tudjuk:

b(K) ≤ x_{2} < b(I) ≤ x_{1} ≤ b(k) < y_{1} ≤ b(i) < y_{2} ≤ j(K) < j(I)

Azt akarjuk, hogy F′ szigorúan több sovány párt fogjon le, mint F. E felírásoból látszik, hogy f′_{1} lefogja (I, i)-et, akit F nem fogott le. Az alábbi lemmát kell tehát még belátni:

4.3.2. Lemma. Ha F lefogott egy (I′, i′) sovány párt, akkor ezt F′ is lefogja.

Bizonyítás. Baj csak akkor lehet, ha (I′, i′)-t F -nek csak egyetlen éle fogta le, és ez f_{1} volt vagy f_{2}. Minden más esetben F′ triviálisan le fogja őt fogni.

Ha ez az egyetlen él f_{2}, akkor a fenti felírásból következik, hogy vagy f′_{1}, vagy f′_{2} fedni fogja őt. Ha pedig f_{1} az egyetlen (I′, i′)-t lefogó él, akkor tegyük fel indirekten, hogy sem f′_{1}, sem f′_{2} nem fogja le őt. Abból, hogy f′_{1} nem fogja le, következik, hogy j(I′) < y_{2}, abból pedig, hogy f_{2} nem fogja ke, azt kapjuk, hogy b(I′) > x_{2}. Ekkor azonban k ∈ I′ ⊂ K ellentmondásban azzal, hogy (K, k) sovány pár volt. □

4.3.1. A súlyozott eset

Az előbbi algoritmust Frank András a 3.2.11. tételre is általánosította ([9]). Legyen adott egy w nemnegatív egész értékű súlyozás az éleken. Az algoritmus megadja U-nak egy minimális w-generátorát, és reprezentált utaknak egy ugyanakkora súlyú független rendszerét. (Ezen fogalmak definíciói a 3.2.5 fejezet végén találhatóak.) Legyen E^{∗} az összes v_{i}v_{j} (i < j) élek halmaza. Legyen F egy (esetleg többszörös éleket is tartalmazó) élrendszer. Ezt egy z : E^{∗} → Z_{+} vektorban fogjuk tárolni, ahol z(e) azt fejezi ki, hogy az e él hányszor szerepel F -ben. Legyen |z| := ∑_{e∈E^{∗}} z(e).

Jelöjük ρ_{z}(I, f)-fel az (I, f)^{−}-ból (I, f)^{+}-ba menő F -beli élek számát. Legyen az (I, f) pár súlya w(I, f) = w(f). Mondjuk azt, hogy z w-fedi az (I, f) párt, ha ρ_{z}(I, f) ≥ w(I, f). Legyen az (I, f) pár z-hiánya def(I, f) = (w(I, f) − ρ_{F} (I, f))^{+}. def(I, f) > 0 esetén nevezzük (I, f)-et hiányos párnak.

Az algoritmus a sovány reprezentált utak L_{U} rendszerének egy z minimális w-fedését fogja megadni (azaz ami minden elemet w-fedni fog). A 3.2.9 lemma könnyen láthatóan érvényben marad erre az esetre is, tehát z U_{r}-t is w-fedni fogja. Innen a szokásos módon kaphatjuk U-nak egy w-generátorát: minden xy ∈ E^{∗} élhez z(xy) példányban vegyünk egy olyan utat, aminek a kezdőpontja x, a végpontja y. Szükségünk lesz az alábbi lemmára:

4.3.3. Lemma. Legyenek (X, i) és (Y, j) keresztező sovány párok. Ha a (K, k) sovány pár egyiküket sem keresztezi, akkor nem keresztezi sem (X, i) ∨ (Y, j)-t, sem (X, i) ∧ (Y, j)-t.

Ezt rögtön egy kicsit általánosabb esetben látjuk be:

4.3.4. Lemma. Legyenek X = (X^{−}, X^{+}), Y = (Y^{−}, Y^{+}) keresztező párok, K = (K^{−}, K^{+}) egy további pár. Tegyük fel, hogy K nem keresztezi sem X-et, sem Y -t. Ekkor nem fogja keresztezni X ∨ Y -t és X ∧ Y -t sem.

Bizonyítás. Tegyük fel először, hogy K összehasonlítható mind X-szel, mind Y -nal. K ⪯ X és Y ⪯ K nem lehet, mivel ebből Y ⪯ X adódna, ellentmondásban azzal, hogy keresztező párok. A szimmetria miatt feltehetjük, hogy K ⪯ X, Y. Ekkor azonban K ⪯ X ∨ Y, K ⪯ X ∧ Y, amiből az állítás következik.

Másodszor vizsgáljuk azt az esetet, amikor K mind X-től, mind Y -tól független. A szimmetria miatt feltehetjük, hogy X^{−} ∩ K^{−} = ∅. Ekkor K^{−} ∩ (X^{−} ∩ Y^{−}) = ∅, vagyis X ∧Y mindenesetre független K-tól. Ha Y^{−}∩K^{−} = ∅, akkor K^{−}∩(X^{−}∪Y^{−}) = ∅ biztosítja X ∨ Y és K függetlenségét; ha pedig Y^{+} ∩ K^{+} = ∅, akkor ugyanez K^{+} ∩ (X^{+} ∩ Y^{+}) = ∅ miatt lesz igaz.

Tegyük most fel, hogy K pontosan az egyiküktől független. Legyen mondjuk független X-től, és legyen Y -nal összehasonlítható. A szimmetria miatt föltehetjük, hogy X^{−} ∩ K^{−} = ∅, amiből ismét az fog következni, hogy X ∧ Y független K-tól. Mivel K és Y összehasonlíthatók, X és Y pedig keresztezők, ezért X^{−} ∩ K^{−} = ∅ csak úgy lehet, ha K ⪯ Y. Viszont Y ⪯ X ∨ Y, tehát K ⪯ X ∨ Y, ismét készen vagyunk. □

A minimális w-fedéssel együtt az algoritmus meg fog adni egy ugyanakkora összsúlyú független elemekből álló rendszert is. A három fázis az előző algoritmus fázisainak fog megfelelni:

1. fázis Egy I váz meghatározása. Most az e_{i} élek w-súlya szerinti csökkenő sorrendben megyünk végig. Azaz egy olyan teljes rendezését tekintjük L_{U}-nak, melyben (K, k) megelőzi (J, e)-t, amennyiben w(k) = w(K, k) > w(J, e) = w(e).

Ebben a sorrendben mohón építjük fel az I vázat: a soron következő elemet akkor vesszük be, ha nem keresztez egyetlen addig beválasztott elemet sem.

Legyenek a végső I elemei (K_{1}, k_{1}), (K_{2}, k_{2}), …, (K_{N}, k_{N}), a beválasztás sorrendjében. Minden (J, j) ∈ L_{U} − I-re van I-nak egy (J, e)-t keresztező eleme. Legyen l = t(J, j) a legkisebb olyan index, amelyre (K_{l}, k_{l}) keresztezi (J, e)-t.

2. fázis A 2.3.2. súlyozott Dilworth-algoritmussal meghatározzuk I-nak egy K maximális súlyú páronként nem összehasonlítható elemekből álló részét és egy minimális súlyozott láncfelbontásnak megfelelő z fedést úgy, hogy w(I) = |z|.

3. fázis Ha F w-fedi L_{U}-t is, akkor készen vagyunk. Ha nem, akkor z-t úgy fogjuk változtatni, hogy a |z| ne nőjön, és L_{U} elemeinek z-hiány összege csökkenjen.

Ehhez tekintsük az a (I, i) hiányos sovány párt, melyre t(I, i) a legnagyobb. Legyen (K, k) := (K_{t(I,i)}, k_{t(I,i)}). (I, i) és (K, k) tehát keresztezni fognak.

Feltehetjük, hogy k megelőzi i-t. (Ha nem így volna, fordítsuk meg a P út irányítását és vele az összes élt és minden (X, x)-re cseréljük fel (X, x)^{−}-t és (X, x)^{+}-t.)

E feltételezés mellett (K, i) = (I, i) ∨ (K, k) és (I, k) = (I, i) ∧ (K, k) A 3.2.8 lemma szerint L_{U} keresztező rendszer. Ígyhát (K, i) és (I, k) is sovány párok lesznek.

4.3.5. Állítás. F w-fedi mind (K, i)-t, mind (I, k)-t.

Bizonyítás. Tegyük fel, hogy def(I, k) > 0 (a bizonyítás ugyanígy fog menni (K, i)-re). I minden elemét lefogtuk, ezért (I, k) ∉ I. (I, i) választása miatt l′ = t(I, k) ≤ t(I, f). Minthogy (I, k) ⪯ (K, k), ezért itt nem állhat fenn egyenlőség. Tehát (K_{l′}, k_{l′}) nem keresztezi sem (K, k)-t (mindketten I elemei), és t(I, i) definíciója szerint t(I, i)-t sem. Ez azonban ellentmond a 4.3.3 lemmának. □

4.3.6. Állítás. Van olyan f_{1} = x_{1}y_{1} ∈ E^{∗} él, melyre x_{1} ∈ (I, i)^{−} ∩ (K, k)^{−}, y_{1} ∈ (I, i)^{−} ∩ (K, k)^{+}, és z(f_{1}) > 0. Van továbbá egy olyan f_{2} = x_{2}y_{2} ∈ E^{∗} él, melyre x_{2} ∈ (K, k)^{−} − (I, i)^{−}, y_{2} ∈ (I, i)^{+} ∩ (K, k)^{+} és z(f_{2}) > 0.

Bizonyítás. Az 1. fázis során (I, i)-t (K, k) miatt nem választottuk be. Így a sorrendben (K, k) megelőzte (I, i)-t, azaz w(I, k) = w(k) ≥ w(i) = w(I, i). Tudjuk, hogy z nem w-fedi (I, i)-t, fedi azonban (I, k)-t. Kihasználva azt a feltevést, hogy k megelőzi i-t, következik a kívánt f_{1} létezése. Hasonlóan, mivel z w-fedi (K, i)-t és w(I, i) = w(i) = w(K, i), kapjuk a kívánt f_{2} létezését. □

A 3. fázisban tehát a következőt fogjuk csinálni. Kiválasztjuk azt az (I, i)-t, amelyre t(I, i) maximális, és z-t z′-re változtatjuk az alábbi módon. Legyen δ := min(z(f_{1}), z(f_{2})), f′_{1} = x_{1}y_{2}, f′_{2} = x_{2}y_{1}. Legyen z′(f_{1}) = z(f_{1}) − δ, z′(f_{2}) = z(f_{2}) − δ, z′(f′_{1}) = z(f′_{1}) + δ, z′(f′_{2}) = z(f′_{2}) + δ, egyébként pedig legyen z′(f) = z(f). Nevezzük ezt a lépést (I, i) átkeresztezésének.

f_{1} és f_{2} nem fedte, azonban f′_{1} fedni fogja (I, i)-t, ezért világos, hogy def(I, i) csökken. Azt kell hát még megmutatnunk, hogy

4.3.7. Lemma. Minden (I′, i′) sovány párra ρ_{z′}(I′, i′) ≥ ρ_{z}(I′, i′).

Ennek bizonyítása szó szerint megegyezik a 4.3.2 lemma. bizonyításával.

Tehát egy ilyen lépés során az elemek z-hiányösszege szigorúan csökken, azaz véges sok lépésen belül az algoritmus véget ér.

Bonyolultság

Itt most f_{1}-et és f_{2}-t a megadott feltételek mellett tetszőlegesen választhattuk. Ahhoz azonban, hogy erősen polinomiális algoritmust kapjunk, még az alábbi kikötést tesszük: Legyen f_{1} minimális abban az értelemben, hogy az x_{1}y_{1} út a lehető legrövidebb, f_{2} pedig maximális, azaz az x_{2}y_{2} út a lehető leghosszabb.

4.3.8. Állítás. Egy adott (I, i)-t legfeljebb \binom{n}{2} alkalommal keresztezünk át.

Bizonyítás. Egy átkeresztezés során vagy z(f_{1}), vagy z(f_{2}) nullára csökken. f_{1} és f_{2} minimális illetve maximális választása okán (I, i) további átkeresztezései során z(f_{1}) és z(f_{2}) értéke nem nőhet. Ezért legfeljebb |E^{∗}| = \binom{n}{2} átkeresztezés után (I, i) z-hiánya 0-ra csökken, azaz fedve lesz. □

4.3.9. Állítás. L_{U} ≤ n^{2}.

Bizonyítás. Minden e ∈ P élre és v_{i} ∈ P csúcsra legfeljebb egy olyan sovány (J, e) pár lehet, melyre b(J) = v_{i}. Ebből az következik az állítás. □

Ezen állításokból következik, hogy legfeljebb n^{4} átkeresztezési lépés lehet.

L_{U} ≤ n^{2} miatt ez az első és a második fázis bonyolultságára is felső becslés, azonban a második fázis bonyolultsága O(n^{6}) is lehet.

Benczúr A. András, Jörg Förster és Király Zoltán [10] belátták, hogy egy váznak legfeljebb O(n log n) eleme lehet. Ennek alapján O(nm+n^{2}\sqrt{n log n}) becslés adódik a 2. fázis bonyolultságára. A legjobb becslésük a súlyozatlan esetre O(n^{2.5}log^{3/2}n).

További általánosítások

Az algoritmus elmondható szinte szó szerint ugyanígy arra az esetre, amikor P nem út, hanem kör. Frank András további általánosítása az, hogy ha a w élsúlyozás mellett adott a pontokon egy d_{b} és d_{j} súlyozás. Egy e = (u, v) él behúzásának költsége d_{b}(u) + d_{j}(v), és feladatunk az U legolcsóbb w-fedésének megtalálása. Ehhez mindössze a 2. fázist kell megváltozatni, ahol a minimális költségű súlyozott Dilworth algoritmust kell használni. A 3. fázisban az átkeresztezések során az összköltség nem változik.

4.4. 0-1 értékű szupermoduláris függvény fedése

A 4.3. részben leírt (súlyozatlan) útfedési algoritmus gondolatmenete általánosítható a Szupermoduláris Fedési Tétel azon 3.1.6 esetére, amikor p 0-1 értékű:

4.4.1. Tétel. Ha P halmazpárok keresztező rendszere, akkor a P-t lefogó élek minimális τ(P) száma egyenlő lesz a P páronként független elemeinek maximális ν(P) számával.

Ennek legfontosabb alkalmazása az, amikor adott egy D = (V, A) k − 1-szeresen ST - összefüggő digráf, akit minimális számú él hozzávételével k-szorosan ST -összefüggővé szeretnénk tenni. Ekkor az egyirányú párok P családja keresztező rendszer lesz. Az itt leírt algoritmus Frank András [11] cikkének továbbgondolásából származik. Először leírjuk az algoritmust arra a speciális esetre, amikor k −1-összefüggő gráfot növelünk k-összefüggőre, ezt követi majd az általános eset leírása.

Legyen F keresztező rendszer, és egy K ⊆ F halmazra legyen

F ÷ K := {X ∈ F : X nem keresztezi K-t}

F ÷ K := {X ∈ F : X nem keresztezi K egy elemét sem}

Az alábbi két lemma közül az első a 4.3.4. lemma közvetlen következménye, a második pedig egyszerűen belátható.

4.4.2. Lemma. F ÷ K is keresztező rendszer

4.4.3. Lemma. Ha az f él lefogja X ∨ Y -t vagy X ∧ Y -t, akkor f lefogja X-et vagy Y -t is.

Nevezzünk egy X párt kövérnek, ha létezik olyan tőle különböző Y pár, hogy Y^{−} ⊆ X^{−} és Y^{+} ⊆ X^{+}. A nem kövér párokat hívjuk soványnak. Legyen K ∈ F egy sovány elem, F′ = F ÷ K, és F′ F′ egy fedése. f′_{1} = x_{1}y_{1}, f′_{2} = x_{2}y_{2} legyenek F′ elemei, és legyen

f_{1} := x_{1}y_{2} és f_{2} := x_{2}y_{1}
F′′ := F′ − {f′_{1}, f′_{2}} + {f_{1}, f_{2}}

Mondjuk azt, hogy F′′ F′-ből f′_{1} és f′_{2} átkeresztezésével keletkezik. Nevezzük ezt javító átkeresztezésnek, ha F′′ szigorúan több elemét fedi le F-nek, mint F′ tette. Az algoritmus lényege az alábbi lemma lesz:

4.4.4. Lemma. Legyen F keresztező rendszer, K egy sovány eleme, és F′ F ÷ K egy fedése. Ha F′ nem fedi le F minden elemét, akkor van javító átkeresztezés.

Bizonyítás. Válasszuk az F′ által nem fedett X, Y ∈ F-et úgy, hogy X ⪯ Y, továbbá X minimális abban az értelemben, hogy X′ ≺ X, X′ ∈ F esetén F′ fedi X′-t, és Y ugyanilyen értelemben maximális.

Mivel F′ nem fedi X-et és Y -t, ezért X, Y ∈ F − F′, azaz mindketten keresztezik K-t. Ezért X ∩K ≺ X és Y ∪K ≻ Y. X minimalitása miatt X ∩K-t fedni fogja F′ egy f′_{1} = x_{1}y_{1} éle. Minthogy F′ nem fedi X-et, ezért x_{1} ∈ X^{−} ∩ K^{−}, y_{1} ∈ K^{+} − X^{+}. Hasonlóan, Y ∪ K-t egy olyan f′_{2} = x_{2}y_{2} él fogja fedni, amire x_{2} ∈ K^{−} − Y^{−} és y_{2} ∈ K^{+} ∩ Y^{+}. Legyen f_{1}, f_{2}, F′′ az, amit fentebb definiáltunk.

Megmutatjuk, hogy {f′_{1}, f′_{2}} átkeresztezése javító átkeresztezés lesz. Minthogy F′′ fedi X-et, F′ pedig nem, ezért csak azt kell megmutatni, hogy minden olyan elemet, amit F′ fedett, azt F′′ is fedni fog.

Tegyük fel indirekten, hogy van egy F′ által fedett, de F′′ által nem fedett L elem. Egy F′ − {f′_{1}, f′_{2}}-beli él nem fedheti őt, és az sem lehet, hogy mind f′_{1}, mind f′_{2} fedje. Tehát L-et F′-ben pontosan egy él fedi, méghozzá vagy f′_{1}, vagy f′_{2}. A szimmetria miatt feltehetjük, hogy f′_{1} fedi L-et. (Ezután a feltevés után már csak Y -nal dolgozunk, X-re nem lesz szükségünk.)

4.4.5. Állítás. Y^{+} ∩ L^{+} ≠ ∅

Bizonyítás. Tegyük fel indirekten, hogy Y^{+} ∩ L^{+} = ∅. Tekintsük a Z := [(L ∧ K) ∨ Y] ∧ K elemet. Mivel Y^{+} ∩ L^{+} = ∅, ezért Z^{+} = K^{+} és Z^{−} ⊆ K^{−} − x_{2} ⊂ K^{−}, ellentmondva annak, hogy K sovány. □

Eszerint Y és L nem függetlenek. Nem is összehasonlíthatók, mivel y_{2} ∈ Y^{+} − L^{+} és y_{1} ∈ L^{+} − Y^{+}. Ezért Y ∨ L ≻ Y. Y maximalitása miatt Y ∨ L fedve van F′ egy f elemével. Ez mind f′_{1}-től, mind f′_{2}-től különbözik, mivel y_{1} és y_{2} nincsenek benne L^{+} ∩Y^{+}-ban. Tehát f ∈ F′′ ∩ F′, ami miatt f sem Y -t, sem L-et nem fedheti. Ez azonban ellentmond a 4.4.3 lemmának □

Tegyük fel, hogy adott egy sovány elemekből álló I váz. Ebben a Dilworth algoritmus egy minimális F_{0} fedést és egy ugyanennyi elemű maximális független rendszert ad. Ha F_{0} fedi P ÷ I-t, akkor a 4.4.4. lemma alapján elő tudjuk állítani a teljes P poset ugyanannyi elemű fedését. Egy nem bővíthető vázat hívjunk teljes váznak. Ha I teljes váz, akkor a feltétel teljesülni fog. Általában sajnos nem lesz igaz, hogy létezik sovány elemekből álló teljes váz. Az alábbi speciális esetben azonban igen, mivel minden elem sovány lesz.

4.4.1. Összefüggőség növelése eggyel

Legyen D = (V, A) (k − 1)-összefüggő irányított gráf. Álljon most P a D azon X egyirányú párjaiból, melyekre p_{def}(X) = 1. Könnyen látható, hogy P keresztező rendszer. Mivel minden ilyen X ∈ P-re |V − (X^{−} ∪ X^{+})| = k − 1, ezért P minden eleme sovány.

Teljes váz építése

Egy I vázat nevezzünk alváznak, ha ∀ K ∈ I, Z ≺ K, Z ∉ I esetén I + Z nem váz.

4.4.6. Állítás. Az összes ⪯-ra nézve legnagyobb és legkisebb pár benne van minden teljes vázban.

Bizonyítás. X és Y keresztező párokra X ∨ Y illetve X ∧ Y ⪯-re nézve szigorúan kisebbek ill. nagyobbak X-nél és Y -nál is. Tehát egy legnagyobb vagy legkisebb pár nem keresztezhet senkit. □

Ennek következményeként egy alváz pontosan akkor teljes, hogyha tartalmazza az összes legnagyobb párt. Egyrészt az előző állítás szerint az összes ilyet tartalmaznia kell. Másrészt, ha az összeset tartalmazza és bővíthető, akkor nem lehet alváz, mert tetszőleges párnál van nagyobb a legnagyobb párok közt.

Legyen I ⊆ P alváz és M ∈ P − I egy legnagyobb pár. Legyen

I′ = {L ∈ I|L ⪯ M}; I′′ = I − I′

Azt mondjuk, hogy K ∈ P −I, K ⪯ M M-illik I-hez, ha független I′′ minden elemétől és I′ minden elemét vagy tartalmazza, vagy független tőle. Ha egyértelmű, hogy mi az M, akkor röviden azt mondjuk, hogy K illik I-hez.

Megjegyzés Maga M például egy I-hez illő pár lesz.

4.4.7. Lemma. Ha I alváz, K ∈ P − I, K ⪯ M, akkor ekvivalens az alábbi két állítás:

(i) K illik I-hez, (ii) I + K váz.

Bizonyítás. (i) ⇒ (ii) következik a definícióból. A másik irányban az alváz definíciója miatt világos, hogy semmilyen L ∈ I-re nem lehet K ≺ L. Azt kell még látni, hogy semmilyen L ∈ I′′-re nem lehet L ≺ K. Ez pedig azért igaz, mert belőle L ≺ K ⪯ M miatt ellentmondásra jutnánk I′′ definíciójával. □

4.4.8. Következmény. Ha K ⪯ M egy legkisebb I-hez illő pár, akkor I + K is alváz.

Bizonyítás. I +K mindenesetre váz. Ha nem lenne alváz, az úgy lenne lehetséges, ha volna egy J ≺ K ⪯ M, akire I + J váz. J ⪯ M és így használhatjuk az előző lemmát: eszerint J is illik I-hez. Ez azonban ellentmondás. □

Megvalósítás

Teljes alváz építését tehát úgy tudjuk kivitelezni, hogy kiindulunk az üres halmazból. Ha egy lépésben I tartalmazza az összes legnagyobb elemet, akkor készen vagyunk. Ha viszont létezik M ∈ P − I, akkor az előző lemma alapján I bővíthető úgy, hogy alváz maradjon. Ehhez először is meg kell találnunk a legnagyobb elemeket.

Tartalmazásra nézve legszűkebb és legbővebb minimális st̄ vágások keresése hálózatban

Legyen a H = (U, E) hálózat élein adva egy g ≥ 0 kapacitásfüggvény.

4.4.9. Lemma. Ha adott egy x maximális méretű st folyam, akkor egy halmaz pontosan akkor minimális vágás, ha minden kilépő e élre x(e) = g(e) és minden belépő e élre x(e) = 0

Ebből világos, hogy két minimális st̄ vágás metszete és uniója is minimális st̄ vágás, tehát létezik egyértelmű m tartalmazásra nézve legszűkebb és M legbővebb minimális st̄ vágás, amik az összes minimális st̄ vágás metszeteként ill. uniójaként állnak elő. Az MFMC algoritmus futásának végén adódó minimális vágás éppen m lesz. M-et pl. a fordított gráfon a minimális ts folyamhoz tartozó minimális vágásként kaphatjuk.

Ennek alkalmazása gráfokra

Építsünk a D = (V, A) (k −1)-összefüggő, de nem k-összefüggő gráfhoz egy H = (U, E) hálózatot. Ebben minden x ∈ V pontnak egy x′ kezdő- és egy x′′ végpont feleljen meg. Vegyünk a hálózatba minden x-re egy x′x′′ élt 1 kapacitással és egy x′′x′ élt ∞ kapacitással. Ha xy ∈ A, akkor húzzunk be a hálózatba egy ∞ kapacitású x′′y′ élt. Nevezzünk egy Z vágást valódinak, ha van olyan x, y ∈ V, amire x′′ ∈ Z és y′ ∉ Z. Egy valódi vágás értéke legalább k − 1, hiszen D-ben van eme x és y pontok közt k − 1 pontdiszjunkt út, amiknek a hálózatban értelemszerűen egy k − 1 értékű x′′y′ folyam felel meg.

Egy Z minimális értékű valódi vágáshoz tekintsük az X_{Z} = {x ∈ D|x′, x′′ ∈ Z} és Y_{Z} = {y ∈ D|y′, y′′ ∉ Z} csúcshalmazokat V -ben. Ekkor (X_{Z}, Y_{Z}) ∈ P. Ugyanis ha valamely x ∈ X_{Z}-ből menne él egy y ∈ Y_{Z}-be, akkor a hálózatban az x′′y′ végtelen kapacitású él kilépne Z-ből. Továbbá |V −(X_{Z} ∪Y_{Z})| = k−1, hiszen e halmazban azok a pontok vannak, akiknek hálózatbeli kezdőpontja Z-ben, a végpontja U − Z-ben van. Az ő számuk k − 1, mivel a vágás értéke is ennyi.

Megfordítva, tetszőleges (X^{−}, X^{+}) ∈ P-nek H-ban megfelel egy Z minimális értékű valódi vágás: Z = {x′, x′′|x ∈ X^{−}} ∪ {x′|x ∈ V − (X^{−} ∪ X^{+})}

Mondjuk azt, hogy X ∈ P egy xȳ pár, ha x ∈ X^{−}, y ∈ X^{+}. Egy ⪯-ra nézve legkisebb (legnagyobb) X ∈ P xȳ párnak H-ban egy tartalmazásra nézve legszűkebb (legbővebb) x′′ȳ′ minimális értékű valódi vágás felel meg. Minthogy az ilyen vágások mind valódiak, e feladat az előző pontban tárgyalt módon elvégezhető.

Az összes legnagyobb P-beli elem megkereséséhez tetszőleges x, y ∈ V párra keresünk ⪯-ra nézve legnagyobb olyan (X^{−}, X^{+}) ∈ P párt, amire x ∈ X^{−} és y ∈ X^{+}, és ezek halmazából tekintjük a legnagyobbakat.

Alvázbővítés

Ezek után leírjuk az alváz bővítésének egy lépését.

4.4.10. Állítás. Egy I vázban tetszőleges N párnál kisebb párok tövei lamináris rendszert alkotnak.

Bizonyítás. Legyen L, J ⪯ K. Vagy L ⪯ J, vagy J ⪯ L, vagy pedig függetlenek. Ez utóbbi esetben a töveik diszjunktak, hiszen L^{+} ∩ J^{+} ⊇ N^{+} ≠ ∅ □

Használjuk az alábbiakban a 4.4.1. szakasz jelöléseit! Legyenek L_{1}, ..., L_{r} az I′-beli legnagyobb elemek, az ő töveik az előző állítás szerint M^{−} páronként diszjunkt részhalmazai. Húzzuk be a D = (V, A) gráfba az összes olyan élt, ami valamely I′′-beli pár tövéből a fejébe megy. Legyen az így kapott gráf D′ = (V, A′).

4.4.11. Állítás. Legyen J D-ben egyirányú pár. Pontosan akkor lesz D′-ben is az, ha I′′ valamennyi elemétől független.

Bizonyítás. Két egyirányú pár pontosan akkor fogható le egy éllel, ha nem függetlenek. Abból, hogy hozzávett élek mindegyike lefogja I′′ egy elemét, következik az állítás. □

Tehát K ∈ P − I, K ⪯ M pontosan akkor illik I-hez, ha D′-ben is egyirányú pár, és tetszőleges i = 1, ..., r-re L_{i}-re L_{i} ≺ K vagy L_{i} és K függetlenek. A 4.4.8. következmény szerint I bővíthető egy olyan K párral, amely ezeket a feltételeket kielégíti és tartalmazásra nézve minimális.

Készítsük most el a fentebb leírt módon a H′ hálózatot a D′ gráfhoz! A H′′ ettől még annyiban különbözzön, hogy minden i = 1, ..., r-re tetszőleges x, y ∈ L_{i}^{−}-hoz húzzuk be az x′′y′′ élt ∞ kapacitással. Az így kapott hálózat valódi minimális vágásai éppen az L_{i} pároknak és I-hez illő pároknak felelnek meg. Ez utóbbiak közül kell tartalmazásra nézve minimálisat keresnünk.

Legyen C_{1} = M^{−} \ ∪_{i=1}^{r}L_{i}^{−}. Ha C_{1} = ∅, akkor legyen R_{1} = M, egyébként válasszunk tetszőleges x_{1} ∈ C_{1}-t. Legyen R_{1} H′′-ben tartalmazásra nézve legszűkebb x′′_{1}ȳ′_{1} vágáshoz tartozó egyirányú pár.

Ezután minden lépésben legyen C_{i+1} = R_{i}^{−} \ (∪_{i=1}^{r}L_{i}^{−} ∪ {x_{1}, x_{2}, ..., x_{i}}). Ha C_{i+1} ≠ ∅, akkor legyen x_{i+1} ∈ C_{i+1}. Legyen R_{i+1} H′′-ben a tartalmazásra nézve legszűkebb x′′_{i+1}ȳ′ vágásnak megfelelő egyirányú pár.

Tegyük fel, hogy C_{i+1} = ∅. K ≺ R_{i} akkor lehet I-hez illő, ha K töve legalább két L_{j} ⊂ R_{i} halmaz uniójaként áll elő.

Ezért a következő fázisban válasszunk minden L_{j} ⊂ R_{i}-ra egy z_{j} ∈ L_{j} pontot, és minden j < l párra készítsük el H′′-ből a z′′_{j}z′_{l} ∞ kapacitású él hozzávételével a H_{jl} hálózatot, és tekintsük ebben a tartalmazásra nézve legszűkebb z′′_{j}ȳ′ vágásnak megfelelő egyirányú párt. Ezek közül egy tartalmazásra nézve minimálisat választva egy megfelelő K halmazt kapunk.

Vázbontás

Az előző pontban meghatároztunk egy I teljes alvázat. Legyenek ennek elemei a hozzávétel sorrendjében K_{1}, K_{2},..., K_{m}, és legyen I_{j} = {K_{1}, ..., K_{j−1}}, valamint F_{j} = P ÷ I_{j}.

A Dilworth-algoritmussal ebben meg tudunk határozni egy minimális F′ fedést és egy maximális antiláncot, ami a váztulajdonság alapján éppen egy maximális független rendszer lesz.

Ezután az alábbi Full-Flip [11] szubrutint fogjuk használni:

Bemenet: F_{j+1} = F_{j} ÷ K_{j} egy F′ fedése.

Kimenet: F_{j}-nek egy |F′| elemű fedése.

Amíg F′ nem fedi F_{j}-t, válasszunk X, Y ∈ F_{j} fedetlen elemeket úgy, hogy X ⪯ Y, és X minimális, Y pedig maximális ilyen tulajdonságú elem (az 4.4.2. lemmában leírt értelemben.) Válasszunk egy X ∧ K_{j}-t fedő f′_{1} ∈ F′ és egy Y ∨ K_{j}-t fedő f′_{2} ∈ F′ élt. F′-ben keresztezzük át {f′_{1}, f′_{2}}-t.

E szubrutin az 4.4.2. lemma értelmében helyesen működik. Induljunk ki j = m-ből! Mivel I teljes alváz, ezért nincs olyan pár, aki minden elemétől független lenne, így F_{m} = ∅. Ezután a fenti szubrutin használatával minden lépésben megadjuk F_{j} egy fedését, j = m − 1, ..., 0. F_{0} = P, tehát végül egy jó fedést fogunk kapni.

A kivitelezés során X és Y találása az egyetlen nem triviális lépés. Válasszunk egy K_{j} ⪯ M legnagyobb párt és egy x ∈ M^{−} pontot. Olyan ⪯-ra nézve legkisebb és legnagyobb, F′ által nem fedett X(x, M), Y (x, M) ∈ F_{j}-t fogunk keresni, amik kisebbek M-nél és töveik tartalmazzák x-et. Legyen D_{1} = (V, A + F′). Az alábbi állítás a 4.4.7. lemma triviális következménye.

4.4.12. Állítás. Ha Z ⪯ M olyan egyirányú pár D-ben, amit F′ nem fed le, és I_{j} + Z váz, akkor Z D_{1}-ben M-illik I_{j}-hez.

Keressünk tehát - amennyiben léteznek - X(x, M) legkisebb és Y (x, M) legnagyobb I_{j}- hez M-illőt, aminek töve tartalmazza x-et. Ennek megvalósításához készítsük el a Vázépítés részben leírt módon a H′′ segédgráfot D_{1}-hez. Legyen y_{0} ∈ M, és keressünk legszűkebb és legbővebb xȳ_{0} vágást. X(x, M) és Y (x, M) legyenek az ezeknek megfelelő párok.

Végezzük el ezt az összes (x, M) párra. Ha egyikre sem létezik X(x, M) és Y (x, M), akkor F′ fedi F_{j}-t. Ha néhány (x, M) párra léteznek, akkor legyen (x_{0}, M_{0}) olyan, amire Y (x_{0}, M_{0}) ezek közül ⪯-ra legnagyobb, és ezen belül X(x, M_{0}) legkisebb.

4.4.13. Állítás. X′ ⪯ X(x, M_{0}), X′ ∈ F_{j} esetén F′ fedi X′-t.

Bizonyítás. Tegyük fel, hogy létezik a feltételt kielégítő X′, amit F′ nem fed. Ekkor valamely (x′, M′) párra X(x′, M′) ⪯ X′ ≺ X(x_{0}, M_{0}). Ekkor x′ ∈ Y (x_{0}, M_{0})^{−} s emiatt Y (x′, M_{0}) ⪰ Y (x_{0}, M_{0}). X(x′, M′) ≺ X(x_{0}, M_{0}) ⪯ M_{0} miatt X(x′, M_{0}) ⪯ X(x′, M′) ≺ X(x_{0}, M_{0}) következne, vagyis (x′, M_{0}) ellentmond (x_{0}, M_{0}) választásának. □

Tehát X(x_{0}, M_{0}), Y (x_{0}, M_{0}) ki fogja elégíteni a Full-Flip algoritmus feltételét.

Bonyolultság

Az összes legnagyobb vágás megtalálása tehát O(n^{2}MC). [1] 4.7 kövekezményéből tudjuk, hogy van diszjunkt utakból és körökből álló minimális növelő halmaz, tehát az 4.4.2 tétel szerint egy maximális független rendszer mérete legfeljebb n. Egy lánc mérete legfeljebb n, így a Dilworth-tétel polárisa szerint |I| ⪯ n^{2}. Így n^{2} növelési lépés van. Minden lépésnél legfeljebb n + \binom{n}{2}-szer keresünk minimális vágást, azaz összesen O(n^{7}) lépést teszünk I felépítéséhez.

Könnyen látható, hogy átkeresztezésből legfeljebb O(n^{3}) lehet, és egy átkeresztezés során O(n^{2}) (x, M) párt választunk, és mindegyikre X, Y keresése 2 MFMC végrehajtásával történik, azaz Full-Flip lépésszáma O(n^{5}MC). Így az összbonyolultság O(n^{5}MC) = O(n^{8}).

4.4.2. Az általános eset

Könnyen mutatható ellenpélda arra, hogy az általános esetre a fenti algoritmus nem működik helyesen. Általában a legnagyobb és legkisebb elemek sem feltétlenül soványak, tehát nem lesz csupa sovány elemből álló teljes váz. Ezért bevezetünk egy, a soványságnál gyengébb fogalmat. Nevezzük K ∈ P-t soványfejűnek, ha nincs olyan Z ∈ P, amire Z^{−} = K^{−}, Z^{+} ⊂ K^{+}. A nem soványfejű párokat nevezzük kövérfejűnek.

Megjegyzés: Egy soványfejű pár nem feltétlenül sovány. Igaz azonban, hogy az összes legnagyobb pár soványfejű, hiszen ha van ilyen Z, akkor K ≺ Z.

Világos, hogy tetszőleges K elemre létezik soványfejű L, amire L^{−} = K^{−}, L^{+} ⊆ K^{+}. Nevezzük az ilyen L-eket K fejredukáltjainak. K fejredukáltjai páronként fejdiszjunkt párok lesznek.

Egy soványfejű elemekből álló I vázat nevezzünk soványfejű alváznak, ha ∀ K ∈ I, Z ≺ K, Z ∈ P ÷I −I esetén Z kövérfejű. Egy nem bővíthető soványfejű alvázat nevezzünk teljes soványfejű alváznak.

4.4.14. Lemma. Legyen I teljes soványfejű váz, és F′ I egy fedése. Ekkor F′ fedi P ÷I-t.

Bizonyítás. Tegyük fel, hogy Z ∈ P ÷ I, és F′ nem fedi Z-t. Legyen J Z egy fejredukáltja. Ha J ∈ I, akkor F′ lefogja J-t, és így lefogja Z-t is.

Ha viszont J ∉ I, akkor J keresztez egy L ∈ I elemet. Ekkor Z és L is összefüggők. Megmutatjuk, hogy nem lehet Z ≺ L, sem L ≺ Z, azaz L és Z keresztezők, ami miatt Z ∉ P ÷ I. L ≺ Z esetén L ≺ Z ⪯ J ellentmond annak, hogy J keresztezi L-et. Tegyük most fel, hogy Z ≺ L. Ekkor J^{−} = Z^{−} ⊆ L^{−}. L és J keresztezése miatt L^{+} ∩ J^{+} ≠ ∅, L^{+} − J^{+} ≠ ∅. Ezért (L ∨ J)^{−} = L^{−}, (L ∨ J)^{+} ⊂ L^{+}, ellentmondva L soványfejűségének. □

Ha sikerül találni egy teljes soványfejű alvázat, akkor onnantól el tudjuk végezni a vázbontást. Az előző lemma szerint kiinduláskor F′ fedi P ÷ I-t, és azt állítjuk, hogy utána minden lépésben használni fogjuk tudni a 4.4.4. lemmát.

Vizsgáljuk meg ugyanis e lemma alkalmazását F = F_{j} = P ÷I_{j}, K = K_{j} esetén! Abban az esetben, ha L-et f′_{1} fedi, akkor Z = [(L∧K_{j})∨Y]∧K_{j} létezéséből jutunk ellentmondásra, ugyanis Z^{+} = K_{j}^{+} és Z^{−} ⊂ K_{j}^{−}. Ha pedig L-et f′_{2} fedi, akkor Z′ = [(L ∨ K_{j}) ∧ Y] ∨ K_{j} adja az ellentmondást Z′^{−} = K_{j^{−}} és Z′^{+} ⊂ K_{j}^{+} révén. K_{j}-ről tehát a soványsága helyett elég annyit feltételezni, hogy nincs olyan Z ∈ F_{j}, akire vagy Z^{−} = K_{j}^{−}, Z^{+} ⊂ K_{j}^{+}, vagy Z^{−} ⊂ K_{j}^{−}, Z^{+} = K_{j}^{+}. Az előbbi eset ellentmondana K soványfejűségének. Azt utóbbi esetben ha Z soványfejű, ez Z ≺ K miatt ellentmond a soványfejű alváz tulajdonságnak. Ha Z kövérfejű, akkor legyen Z′ Z egy fejredukáltja. Ekkor (Z′∨K_{j})^{−} = K_{j}^{−}, (Z′∨K_{j})^{+} ⊂ K_{j}^{+}, ellentmondva K_{j} soványfejűségének.

Soványfejű alváz építése

Feladatunk tehát egy teljes soványfejű alváz találása. A 2.1 részhez hasonlóan látható, hogy egy soványfejű alváz pontosan akkor teljes, ha tartalmazza az összes legnagyobb párt. Hiszen - mint megjegyeztük - minden legnagyobb pár soványfejű, tehát benne vannak minden soványfejű vázban.

Határozzuk meg először az összes legnagyobb elemet. Kezdetben legyen I = ∅. Ha egy lépésben I tartalmazza az összes legnagyobb elemet, akkor készen vagyunk. Egyébként minden M ∈ P − I legnagyobb párra keressünk egy K′(M) legkisebb I-hez M-illő párt. Legyen közülük K′ olyan, akire K′^{−} minimális. Legyen K K′ fejredukáltjainak halmaza.

4.4.15. Lemma. I + K soványfejű alváz.

Bizonyítás. I +K mindenesetre soványfejű váz. Tudjuk egyrészt, hogy elemei soványfejűek. Másrészt tetszőleges L ∈ I-re vagy L ≺ K′, vagy L és K′ függetlenek. Ha tehát K ∈ K, akkor az előbbi esetben L ≺ K′ ⪯ K, az utóbbiban L és K′ függetlenek. Továbbá K független K összes többi elemétől is.

Azt kell még belátni, hogy K ∈ K esetén nincs olyan J ≺ K soványfejű elem, akire J ∈ P ÷ I − I. Tegyük fel, hogy J ilyen. Legyen M′ ⪰ J legnagyobb pár, ekkor J I-hez M′-illő pár lesz. K′ választása miatt nem lehet J^{−} ⊂ K′^{−}, ezért J^{−} = K′^{−}. Ekkor azonban J^{−} = K′^{−} = K^{−} és J^{+} ⊃ K^{+}, ellentmondva J soványfejűségének. □

ST-összefüggőség

A legfontosabb példa az ST-összefüggőség. Legyenek a D = (V, A) gráfban adottak az S és T nemüres halmazok, és tegyük fel, hogy D bármely x ∈ S és bármely y ∈ T pontja közt lokálisan k − 1 összefüggő. Feladatunk az, hogy minimális számú ST él hozzávételével S és T közt k-összefüggővé tegyük.

A 3.2.3. részben leírtakat fogjuk felhasználni: egy X ∈ A(V, V) ST -párra p_{D}(X^{−}, X^{+}) := (k − δ(X^{−}, X^{+}) − h(X^{−}, X^{+}))^{+}. Feltételezésünk szerint p_{D}(X) ≤ 1. Álljon P̂ azon X ST - párokból, melyekre p_{D}(X) = 1, nevezzük ezeket hiányos párnak. Legyen P a P̂ vetítése A(S, T)-re, vagyis álljon P azon X ∈ A(S, T) párokból, melyekhez létezik olyan X̂ ∈ P̂, hogy X^{−} = X̂^{−} ∩ S, X^{+} = X̂^{+} ∩ T. Nevezzük X̂-et X ősének (ez nem feltétlenül egyértelmű). Világos, hogy mind P̂, mind P keresztező rendszerek. Feladatunk most P̂ fedése.

X pontosan akkor lesz ⪯-ra legkisebb (legnagyobb) P-beli pár, ha van olyan X̂ őse, aki P̂-ben ⪯-ra legkisebb vagy legnagyobb. Ezért a legkisebb (legnagyobb) P-beli párok megtalálásához elegendő megkeresni a legkisebb (legnagyobb) párokat P̂-ben. Ehhez a 4.4.1. részben leírt H hálózat helyett azt a hálózatot kell vennünk, ami a 2.2.2. tétel bizonyításában szerepel: legyen a kapacitásfüggvény olyan, hogy g(x′x′′) = 1, g(x′′y′) = 1 minden xy ∈ A-ra. Könnyen látható, hogy ezen hálózat legszűkebb/legbővebb minimális s′′t′ vágásai s ∈ S és t ∈ T esetén éppen a legkisebb/legnagyobb P̂-beli st̄pároknak felelnek meg.

A vázépítés tehát a 0-1 esethez hasonlóan végezhető, egészen K′ megtalálásáig. Feladatunk még K′ összes fejredukáltjának meglelése. Adott y ∈ K′^{+}-ra nyilván létezik egyértelmű legszűkebb K_{y}, amire K_{y}^{−} = K′^{−}, K_{y}^{+} ⊆ K′^{+} és y ∈ K_{y}^{+}. Minden y ∈ K′^{+}-ra határozzuk meg K_{y}-t; ezek halmazából a tartalmazásra nézve legkisebb fejű elemek éppen K′ fejredukáltjai lesznek. K_{y} meghatározásához legyen x_{0} ∈ K′^{−}, és legyen D_{y} az a gráf, amit D-ből kapunk minden z ∈ S − K′^{−}-ra k darab zy él hozzávételével.

4.4.16. Állítás. Ha D_{y}-ban Y a legnagyobb x_{0}ȳ hiányos pár, akkor Y a K_{y} egyik őse.

Ezzel a vázépítést el tudjuk végezni. A vázbontás során ugyanazt kell csinálni, mint a 0-1 esetben, eltekintve attól, hogy e másik típusú hálózatot kell használni. Az összbonyolultság tehát ez esetben is O(n^{6}MC) lesz.

4.5. k-összefüggővé növelés fix k esetén

Az alábbi algoritmus Frank András és Jordán Tibor munkája ([3]). Legyen k ≥ 2 rögzített érték. Egy D = (V, A) irányított gráfot szeretnénk minimális számú új él hozzávételével k-összefüggővé tenni. Idézzük fel a 3.2.4 tételt:

4.5.1. Tétel. A D = (V, A) irányított gráf akkor és csak akkor tehető legfeljebb γ él hozzávételével k-összefüggővé, ha minden egyirányú párokból álló F független családra

∑(p_{def}(X) : X ∈ F) ≤ γ

Az irányított élösszefüggőség növelésével ellentétben (3.2.1 szakasz) itt sem lesz mindig igaz, hogy az optimális duális megoldás vagy páronként fejdiszjunkt, vagy páronként tődiszjunkt párokból áll. Be fogjuk látni azonban, hogy amennyiben az optimum értéke k-tól függően elég nagy, akkor van ilyen szerkezetű duális optimum. Az algoritmus ezt fogja kihasználni.

4.5.1. Az optimális megoldások szerkezete

Nevezzük az X = (X^{−}, X^{+}) párt kisfejűnek, ha |X^{+}| ≤ |X^{−}|. Hasonlóképpen legyen X kistővű, ha |X^{+}| ≤ |X^{−}|. Az alábbi lemmát nem bizonyítjuk.

4.5.2. Lemma ([3], 7. lemma). Van olyan F egyirányú párokból optimális duális megoldás, amelyben a kisfejű párok páronként fejdiszjunktak, a kistövűek pedig páronként tődiszjunktak.

Mi most csak arra a speciális esetre bizonyítunk, amikor a D gráfról feltesszük, hogy eleve (k − 1)-összefüggő. Minden X egyirányú párra p(X) ≤ 1, azaz h(X) ≥ k − 1. Ha p(X) = 1, h(X) = k − 1, akkor nevezzük X-et szorosnak. A szoros párok családjáról könnyen látható, hogy keresztező lesz, sőt, fennállnak az alábbi tulajdonságok is:

4.5.3. Állítás. Legyen X és Y két (nem feltétlenül keresztező) szoros egyirányú pár. Ekkor (i) |X^{+} ∪ Y^{+}| + |X^{−} ∩ Y^{−}| ≤ n − (k − 1) (ii) |X^{+} ∩ Y^{+}| + |X^{−} ∪ Y^{−}| ≤ n − (k − 1)

A 4.5.2 lemmánál egy kicsit erősebb állítás is igaz lesz:

4.5.4. Lemma. Ha D (k − 1)-összefüggő, X és Y független szoros párok, és |X^{+}| ≥ |Y^{−}|, akkor X és Y tődiszjunktak. Ha pedig |X^{−}| ≥ |Y^{+}|, akkor X és Y fejdiszjunktak.

Bizonyítás. A szimmetria miatt elég az első állítást igazolni. Tegyük fel, hogy |X^{+}| ≥ |Y^{−}|, ám mégis X^{−} ∩ Y^{−} ≠ ∅. Mivel X és Y függetlenek, ekkor X^{+} ∩ Y^{+} = ∅. Legyen C_{1} = V − X^{+} − X^{−}, C_{2} = V − Y^{+} − Y^{−}. Az, hogy X és Y pontosak, azt jelenti, hogy |C_{1}| = |C_{2}| = k − 1.

Mivel |X^{−} ∪ X^{+}| = |Y^{−} ∪ Y^{+}| = n − k + 1, ezért a feltételből |X^{−}| ≤ |Y^{+}| következik. C_{2}-t felbontva részekre: k − 1 = |C_{2}| = |X^{−} ∩ C_{2}| + |C_{2} ∩ C_{1}| + |X^{+} ∩ C_{2}|, és a 4.5.3. állítás (i). pontja következtében k − 1 ≤ |Y^{−} ∩ C_{1}| + |C_{2} ∩ C_{1}| + |X^{−} ∩ C_{2}|. Ezekből tudjuk, hogy |C_{1} ∩ Y^{−}| ≥ |C_{2} ∩ X^{+}|. Az |Y^{−}| = |X^{−} ∩ Y^{−}| + |C_{1} ∩ Y^{−}| + |X^{+} ∩ Y^{−}| és |X^{+}| = |X^{+} ∩ Y^{−}| + |C_{2} ∩ X^{+}| felírásból |X^{−} ∩ Y^{−}| > 0 miatt |Y^{−}| > |X^{+}| adódik, ami ellentmondás. □

Abban az esetben, amikor D (k − 1)-összefüggő, e lemma implikálja a 4.5.2 lemmát, méghozzá tetszőleges F-re. Nem bizonyítjuk az alábbi állításokat, melyek közül az utóbbi az approximációs algoritmusban fog szerepet játszani:

4.5.5. Lemma ([3], 3. tétel). Ha D (k − 1)-összefüggő, és az optimum értéke legalább 2k − 1, akkor minden optimális megoldás vagy páronként fejdiszjunkt, vagy páronként tődiszjunkt párokból áll.

4.5.6. Lemma ([3], 4. tétel). Ha D (k − 1)-összefüggő, akkor az optimum értéke legfeljebb k − 1-gyel több a páronként fejdiszjunkt párok maximuma és a páronként tődiszjunkt párok maximuma közül a nagyobbiknál.

Ennek párjaként az általános esetben egy kicsit gyengébb állítás lesz igaz:

4.5.7. Lemma ([3], 9. lemma). Ha az optimum értéke legalább 2k^{2} − 1, akkor van páronként tődiszjunkt, vagy páronként fejdiszjunkt párokból álló optimális duális megoldás.

4.5.2. Ki- és be-hiányok

Vezessük be először a ki-hiány (p_{k}^{o}(H)) illetve be-hiány (p_{k}^{i}(H)) fogalmát. Egy D = (V, A) irányított gráfban egy ∅ ≠ H ⊂ V halmazra legyen

p_{k}^{o}(H) = \{ \begin{matrix}(k − |Γ^{+}(H)|)^{+} & ha H ∪ Γ^{+}(H) ≠ V \\ 0 & egyébként \end{matrix}

p_{k}^{i}(H) = \{ \begin{matrix}(k − |Γ^{−}(H)|)^{+} & ha H ∪ Γ^{−}(H) ≠ V \\ 0 & egyébként \end{matrix}

Világos, hogy p_{k}^{o}(H) = p_{def}(H, V − (H ∪ Γ^{+}(H))) és p_{k}^{i}(H) = p_{def}(V − (H ∪ Γ^{−}(H)), H) amennyiben a pár második (illetve első) tagja nemüres halmaz.

Egy részpartíció ki-hiányán illetve be-hiányán elemei hiányainak összegét értjük. Legyen m_{k}^{o}(D) illetve m_{k}^{i}(D) a részpartíciók ki- illetve be-hiányainak maximuma. Természetesen max(m_{k}^{o}(D), m_{k}^{i}(D)) ≤ N_{k}(D). (N_{k}(D) a független családokon vett p_{def} összegek maximuma.) A 4.5.7 lemma azt mondja ki, hogy ha N_{k}(D) ≥ 2k^{2} − 1, akkor itt egyenlőség áll. Az alábbiakban belátunk két lemmát, ami ezen eset kezelését teszi lehetővé. Ehhez szükségünk lesz az alábbi egyszerű állításra:

4.5.8. Állítás. A Γ^{+} és Γ^{−} függvények szubmodulárisak, azaz bármely H, F ⊆ V -re

|Γ^{+}(H)| + |Γ^{+}(F)| ≥ |Γ^{+}(H ∩ F)| + |Γ^{+}(H ∪ F)|
|Γ^{−}(H)| + |Γ^{−}(F)| ≥ |Γ^{−}(H ∩ F)| + |Γ^{−}(H ∪ F)|

Képezzük most a D^{o} gráfot D-ből egy új s pont, és V -ből s-be mutató új élek hozzávételével. Az új élek E^{o} halmazában minden v ∈ V -ből s-be legfeljebb k párhuzamos él menjen, úgy, hogy a D^{o} = (V + s, A + E^{o}) teljesítse az alábbi követelményt:

minden ∅ ≠ H ⊂ V, V − (H ∪ Γ_{D}^{+}(H)) ≠ ∅ esetén g^{o}(H) ≥ k  (4.8)

ahol g^{o}(H) := |Γ_{D}^{+}(H)| + δ(H, s). (δ(H, s) a H-ból s-be menő E^{o}-beli élek számát jelöli). Az előbbi állítás és δ szubmodularitása miatt g^{o} is szubmoduláris lesz. Világos továbbá, hogy egy ilyen E^{o}-ra m_{k}^{o}(D) ≤ |E^{o}|. Legyen T_{E^{o}} := {v ∈ V : δ(v, s) ≥ 1} az E^{o}-beli élek töveinek halmaza.

4.5.9. Lemma. Legyen D^{o} = (V + s, A ∪ E^{o}) a D = (V, A)-hoz a fenti módon definiált gráf, melyre E^{o} tartalmazásra nézve minimális olyan, hogy eleget tesz a (4.8) feltételnek. Ha |E^{o}| ≥ k^{2} − k + 2, akkor m_{k}^{o}(D) = |E^{o}|.

Bizonyítás. Nevezzünk egy ∅ ≠ H ⊂ V halmazt V − (H ∪ Γ_{D}^{+}(H)) ≠ ∅ és g^{o}(H) = k esetén ki-pontosnak. E^{o} minimalitása miatt minden xs ∈ E^{o} élre létezik x-et tartalmazó ki-pontos halmaz. Így a ki-pontos halmazok uniója lefedi T_{E^{o}}-t. Legyen H = {H_{1}, …, H_{t}} ki-pontos halmazok egy olyan T_{E^{o}}-t fedő rendszere, melyre t minimális. Ha H páronként diszjunkt halmazokból áll, akkor kt = ∑_{i} g^{o}(H_{i}) = ∑_{i} |Γ_{D}^{+}(H_{i})|+δ(H_{i}, s), ahonnan |E^{o}| = ∑_{i} δ(H_{i}, s) = ∑_{i}(k − |Γ_{D}^{+}(H_{i})|) ≤ m_{k}^{o}(D), azaz készen vagyunk.

Tegyük fel, hogy H-nak van két keresztező eleme, H_{i} és H_{j}. Legyen l = |Γ_{D}^{+}(H_{i} ∪ H_{j})|. g^{o} szubmodularitását és (4.8)-at használva az adódik, hogy

k + k = g^{o}(H_{i}) + g^{o}(H_{j}) ≥ g^{o}(H_{i} ∩ H_{j}) + g^{o}(H_{i} ∪ H_{j}) ≥ k + g^{o}(H_{i} ∪ H_{j})  (4.9)

Innen δ(H_{i} ∪ H_{j}, s) ≤ k − l adódik, t minimalitása miatt pedig 1 ≤ δ(H_{i} ∪ H_{j}, s). Ezeket összevetve l ≤ k − 1. Mivel V minden pontjába legfeljebb k új élt húztunk be, azt kapjuk, hogy

δ(H_{i} ∪ H_{j} ∪ Γ_{D}^{+}(H_{i} ∪ H_{j}), s) ≤ kl + (k − l) ≤ k^{2} − k + 1  (4.10)

Ebből |E^{o}| ≥ k^{2} − k + 2 miatt az következik, hogy V − (H_{i} ∪ H_{j} ∪ Γ_{D}^{+}(H_{i} ∪ H_{j})) ≠ ∅, ahonnan (4.8) miatt g^{o}(H_{i} ∪ H_{j}) ≥ k. Ezt (4.9)-be beírva azt kapjuk, hogy H_{i} ∪ H_{j} is ki-pontos halmaz. Ellentmondásra jutottunk t minimális választásával, hiszen H-ból H_{i}-t és H_{j}-t elhagyva és H_{i} ∪ H_{j}-t bevéve T_{E^{o}} kisebb fedését kapnánk. □

Ugyanígy konstruáljuk a D^{i} = (V + s, A ∪ E^{i}) gráfot egy új s pont és és s-ből V -be mutató új élek hozzávételével, úgy, hogy az alábbi tulajdonság teljesüljön:

minden ∅ ≠ H ⊂ V, V − (H ∪ Γ_{D}^{−}(H)) ≠ ∅ esetén g^{i}(H) ≥ k  (4.11)

ahol g^{i}(H) := |Γ_{D}^{+}(H)| + ρ(H, s). Jelölje F_{E^{i}} az E^{i}-beli élek fejeinek halmazát. Az előzőhöz teljesen hasonlóan látható, hogy ha E^{i} tartalmazásra nézve minimális és |E^{i}| ≥ k^{2} − k + 2, akkor m_{k}^{i}(D) = |E^{i}|.

4.5.10. Lemma. Van D-hez olyan optimálisan k-összefüggővé növelő élhalmaz, melynek élei T_{E^{o}}-ból H_{E^{i}}-be mennek.

Bizonyítás. Legyen J olyan optimális növelő élhalmaz, melyre minimális a nem T_{E^{o}}-ból F_{E^{i}}- be menő élek száma. Tegyük fel indirekten, hogy ezek száma pozitív. legyen e = xy ∈ J olyan él, melyre mondjuk x ∉ T_{F^{o}}. A D′ = (V, E ∪ J − e) gráf k − 1-összefüggő lesz és M_{k}(D′) = 1.

A 3.1.6. tétel szerint ekkor létezik egyértelmű ⪯-ra nézve legkisebb és legnagyobb egyirányú szoros pár, X és Y. Ekkor minden e′ = x′y′, x′ ∈ X^{−}, y′ ∈ Y^{+} élre D′ + e′ is k-összefüggő lesz. (4.8) és (4.11) miatt kell hogy létezzen x′ ∈ X^{−} ∩ T_{E^{o}}, y′ ∈ Y^{+} ∩ F_{E^{i}}, tekintettel arra, hogy V −(X^{−} ∪Γ_{D}^{+}(X^{−})) ≠ ∅, V −(Y^{+} ∪Γ_{D}^{−}(Y^{+})) ≠ ∅. Ekkor J −xy+x′y′ is optimális növelő élhalmaz, ami ellentmond J választásának. □

4.5.3. Az algoritmus leírása

1. Fázis Konstruáljunk olyan D^{o} = (V + s, A + E^{o}) segédgráfot, mely kielégíti (4.8)-t és E^{o} tartalmazásra nézve minimális. Ezt úgy tehetjük meg, hogy minden pontból s-be felveszünk k párhuzamos élt, és közülük mohón addig hagyunk el, amíg (4.8) fennáll. Azt, hogy egy él elhagyható-e, úgy tudjuk eldönteni, hogy minden x ∈ V pont és s között az MFMC algoritmussal kiszámítjuk a minimális vágás értékét. Legyen γ_{o} = |E^{o}|. Hasonlóan konstruáljuk meg D^{i}-t is, és legyen γ_{i} = |E^{i}|.

2. Fázis Ha max(γ_{o}, γ_{i}) = 2k^{2}−2, akkor minden lehetséges 2k^{2}−2 méretű T_{E^{o}}-ból F_{E^{i}}- be menő élekből álló J élhalmazra ellenőrizzük, hogy (V, A∪J) k-összefüggő-e. Ha valamely J-re igen, akkor megállunk: ez a J egy optimális növelő élhalmaz lesz. max(γ_{o}, γ_{i}) < 2k^{2}−2 esetén csináljuk ugyanezt, a legfeljebb 2k^{2} − 2 elemű részhalmazokkal, úgy, hogy először megnézzük az összes 1 eleműt, aztán az összes 2 eleműt, s így tovább. A 4.5.10 lemma szerint J mindkét esetben létezni fog.

3. Fázis Ha max(γ_{o}, γ_{i}) ≥ 2k^{2} − 1, akkor minden e = xy T_{E^{o}}-ból F_{E^{i}}-be menő élre ellenőrízzük, hogy N_{k}(D + e) = N_{k}(D) − 1 teljesül-e. Ha igen, akkor vegyük hozzá D-hez, és kezdjük elölről az algoritmust. (Ezt úgy ellenőrízhetjük, hogy D +e-re is meghatározzuk a γ_{o}, γ_{i} értékeket. k ≥ 2 esetén 2k^{2} − 1 ≥ k^{2} − k + 2, ezért a 4.5.7 és a 4.5.9 lemmákat alkalmazva azt kapjuk, hogy N_{k}(D + e) = N_{k}(D) − 1 akkor és csak akkor teljesül, ha max_{(D+e)}(γ_{o}, γ_{i}) = max_{D}(γ_{o}, γ_{i}) − 1.

Bonyolultság

D^{o} és D^{i} meghatározásakor minden élre meg kell vizsgálnunk, hogy kitörölhető-e. Ez egy adott élre n − 1 folyamalgoritmussal végezhető el, tehát az 1. fázis bonyolultsága O(kn^{2}MC).

A 2. fázisban csak k-tól függ a lehetséges J-k száma, f(k) (ez k-nak exponenciális függvénye lesz). Minden J esetén ellenőrízni kell, hogy a kapott gráf k-összefüggő-e, ami n^{2}MC időben tehető, vagy a [18]-ben leírt algoritmus használatával kn^{3} időben. Tehát a 2. fázis futásideje O(f(k)kn^{3}).

A 3. fázisban az xy él vizsgálatakor először meg kell határozni az egyértelmű maximális x-et tartalmazó H_{x} ki-pontos halmazt D^{o}-ban és az y-t tartalmazó maximális H_{y} be-pontos halmazt D^{i}-ben. Ez 2n folyamszámítással végezhető el. Tegyük fel, hogy γ^{0} ≥ γ^{i}. Figyeljük meg, hogy xy akkor és csak akkor nem lesz jó, ha minden x′ ∈ H_{x}-re a G^{o} + xy − x′s gráf megsérti a (4.8) feltételt. Mivel δ(X_{m}, k) ≤ k, ezért ezt kn MFMC algoritmussal meg tudjuk állapítani. A 4.5.10. lemmából könnyen látható, hogy elég kn élt megvizsgálni, így a 3. fázis bonyolultsága O(k^{2}n^{2}MC).

[1] 4.6. lemmája szerint egy maximális független rendszernek legfeljebb n eleme van. Ennek következtében M_{k}(D) ≤ kn, ezért a 2. és 3. fázist összesen legfeljebb kn alkalmommal kell végrehajtani, ígyhát az összbonyolultság O(f′(k)n^{3}MC) = O(f′(k)n^{6}), ahol f′ k-ban exponenciális függvény.

4.6. Approximációs algoritmusok

A 4.5 részben leírt algoritmus kis módosításával polinomiális approximációs algoritmust kaphatunk, mely tetszőleges gráfra legfeljebb 4k^{4}-nel több élt ad meg az optimálisnál. Módosítani mindössze az algoritmus második fázisát kell: itt egyszerűen húzzuk be az összes T_{E^{o}}-ból F_{E^{i}}-be menő élt. A 4.5.10. lemma szerint ez tartalmazni fog optimális növelő élhalmazt, és max(γ_{o}, γ_{i}) ≤ 2k^{2} − 2 miatt az összes behúzott él száma 4k^{4}-nél kevesebb.

Abban az esetben, amikor a kiindulási gráf k − 1 összefüggő, Jordán Tibor lényegesen jobb approximációs algoritmust mutat ([14]), amely az optimális méretű növelő élhalmaznál legfeljebb k − 1-gyel több élt ad meg. Jordán Tibor eredeti algoritmusa az használja ki, hogy ha egy pontnak elég nagy a ki- és befoka is, akkor van leemelhető élpár. Mi leemelések helyett a 4.5 részben belátottakat fogjuk használni. Algoritmusunk szintén legfeljebb k −1gyel több élt fog adni az optimálisnál. (k ≥ 2) A 4.5 rész jelöléseit használva a 4.5.9 lemma helyett az alábbit látjuk be:

4.6.1. Lemma. Legyen D = (V + A) k − 1 összefüggő gráf. D^{o} = (V + s, A ∪ E^{o}) legyen az (4.8) feltételt kielégítő olyan gráf, amelyre E^{o} tartalmazásra nézve minimális. Ha |E^{o}| ≥ k + 1, akkor m_{k}^{o}(D) = |E^{o}|.

Bizonyítás. A bizonyítás teljesen ugyanúgy megy, mint a 4.5.9 lemma esetén. Különbség csupán a (4.10) egyenlőtlenségben lesz. Ott azt használtuk ki, hogy ha E^{o} tartalmazásra nézve minimális, akkor minden x ∈ V -re δ(x, s) ≤ k. Esetünkben azonban δ(x, s) ≤ 1 is igaz lesz. Tehát (4.10) így módosul:

ρ(H_{i} ∪ H_{j} ∪ Γ_{D}^{+}(H_{i} ∪ H_{j}), s) ≤ l + (k − l) ≤ k  (4.12)

Innen |E^{o}| ≥ k + 1 miatt következik, hogy V − (H_{i} ∪ H_{j} ∪ Γ_{D}^{+}(H_{i} ∪ H_{j})) ≠ ∅. □

Bizonyítás nélkül használni fogjuk Mader alábbi eredményét. Egy k-összefüggő gráfban egy élt kritikusnak nevezünk, ha az ő elhagyásával megszünik a k-összefüggőség. Alternáló körnek pedig olyan (irányítatlan értelemben vett) kört nevezünk, mely nem tartalmaz 2 hosszú irányított utat.

4.6.2. Lemma (Mader [17]). Tegyük fel, hogy a D = (V, A) digráf k-összefüggő. Legyen J olyan kritikus élek halmaza, melyek tövének ki-foka és fejének be-foka is legalább k + 1. Ekkor J nem tartalmaz alternáló kört.

4.6.3. Következmény. Legyen D = (V, A) k-összefüggő, és J olyan élhalmaz, hogy D′ = (V, A ∪ J) k + 1-szeresen összefüggő, és J tartalmazásra nézve minimális ilyen. Ekkor J nem tartalmaz alternáló kört.

Bizonyítás. Tegyük fel, hogy J tartalmat egy C alternáló kört. C mindenesetre kritikus élekből áll, hiszen J tartalmazásra nézve minimális. Legyen xy ∈ C tetszőleges él. Mivel d k-összefüggő volt, ezért δ(x) ≥ k + 1, ρ(y) ≥ k + 1. Tehát C-re teljesül a lemma feltétele, ami ellentmondás. □

4.6.4. Következmény. Ha a 4.6.3 következmény feltételei mellett ráadásul J minden éle T_{E^{o}}-ből F_{E^{i}}-be megy, akkor |J| ≤ |T_{E^{o}}| + |F_{E^{i}}| − 1.

Bizonyítás. Készítsük el azt a páros gráfot, melyre minden x ∈ T_{E^{o}} ∪ F_{E^{i}} pontnak egy x és egy x′′ felel meg, és az x′y′′ él pontosan akkor van behúzva, ha x ∈ T_{E^{o}}, y ∈ F_{E^{i}}, és xy él volt az eredeti gráfban. A 4.6.3. következmény szerint J nem tartalmazott alternáló kört, ezért a páros gráfban neki megfelelő élhalmaz körmentes lesz. Ebből következik, hogy |J| ≤ |T_{E^{o}}| + |F_{E^{i}}| − 1. □

4.6.1. Az algoritmus leírása

1. Fázis Csináljuk ugyanazt, mint a 4.5 részben, azzal a különbséggel, hogy elég minden pontból 1 élt húzni s-be.

2. Fázis Ha max(γ_{o}, γ_{i}) ≤ 2k−1, akkor húzzuk be az összes T_{E^{o}}-ből F_{E^{i}}-be menő élt. A 4.5.10. lemma miatt az így kapott gráf k-összefüggő lesz. Hagyjunk el ebből mohón éleket mindössze arra ügyelve, hogy a k-összefüggőség megmaradjon. (Ezt folyamszámításokkal tudjuk eldönteni). A 4.6.4. következmény miatt ezáltal egy legfeljebb γ_{o}+γ_{i}−1 elemű növelő élhalmazt kapunk. Az optimum értéke a 4.5.5. lemma miatt legfeljebb max(γ_{o}, γ_{i}) + k − 1, tehát az optimálisnál legfeljebb k − 1-gyel több élt húztunk be.

3. Fázis Ha max(γ_{o}, γ_{i}) ≥ 2k −1, akkor szintén ugyanazt csináljuk, mint a 4.5 részben, a 4.5.7 és 4.6.1. lemmák helyett a 4.5.5 és 4.5.9 lemmákat használva, tekintettel arra, hogy k ≥ 2 esetén 2k − 1 ≥ k + 1.

Bonyolultság

Az első fázis futásideje O(n^{2}MC), mivel minden pontból csak 1 élt húztunk be s-be. A második fázisban (2k − 1)^{2} élt húzunk be. Mindegyikre egy MFMC végrehajtásával tudjuk ellenőrízni, hogy elhagyható-e, tehát a futásidő O(k^{2}MC). A 3. fázisban a 4.5 rész becslését azáltal javíthatjuk, hogy d(H_{x}, s) ≤ 1, így e fázis futási ideje O(kn^{2}MC) lesz. A már hivatkozott [1] 4.6. következmény miatt M_{k}(D) ≤ n. Tehát összesen a 2. és 3. fázist legfeljebb n-szer hajtjuk végre, ezért az összbonyolultság O(kn^{3}MC) = O(kn^{6}) lesz.

Keresztezőn szupermoduláris függvények fedési algoritmusa

Benczúr András [12] cikkében szerepel a 0-1 értékű szupermoduláris függvény fedési algoritmusa. Az itt leírtak e cikk továbbgondolásából származnak. Ennek nyomán először definiálni fogjuk az erős posetek fogalmát, és kimondunk egy, a Szupermoduláris Fedési Tétellel ekvivalens tételt erős poseteken. Ezután olyan algoritmust adunk meg, amely tetszőleges fedés helyett vagy megad egy eggyel kevesebb elemű fedést, vagy egy optimális duális megoldást. Ez az eredeti probléma megoldására úgy alkalmazható, hogy kiindulunk tetszőleges (pl. mohó) fedésből, és addig ismételjük az algoritmust az egyre kisebb fedésekre, amíg végül minimálisat nem kapnuk. Ezt először a 0-1 értékű szupermoduláris függvény fedésére mondjuk el, a [12]-ben leírtnál sokkal egyszerűbb változatban. Ez talán segíti az általános algoritmus jobb megértését.

5.1. Alapfogalmak

5.1.1. Erős posetek

Legyen (P, ⪯) véges poset. Nevezzük őt erős posetnek az alább felsorolt tulajdonságok fennállása esetén.

u, v ∈ P-t nevezzük összefüggőnek, ha léteznek m, M, amire m ⪯ u ⪯ M és m ⪯ v ⪯ M, egyéb esetben hívjuk őket függetlennek. Tegyük fel, hogy minden u, v ∈ P összefüggő párra az alábbi két művelet egyértelműen van definiálva:

u ∨ v = min{x : x ⪰ u, x ⪰ v}; u ∧ v = max{x : x ⪯ u, x ⪯ v}

Ha m minimális és M maximális elem, akkor az {x : m ⪯ x ⪯ M} halmazt nevezzük [m, M] intervallumnak. Legyen igaz az erős intervallum tulajdonság: minden [m, M] intervallumra

ha u ∨ v ∈ [m, M] vagy u ∧ v ∈ [m, M], akkor u ∈ [m, M] vagy v ∈ [m, M]

Megmutatjuk, hogy a keresztező halmazpár-rendszerek erős posetet alkotnak a rajtuk definiált rendezésre.

5.1.1. Lemma. Egy Q keresztező rendszer párjai erős posetet alkotnak az alábbi rendezésre: (X^{−}, X^{+}) ⪯ (Y^{−}, Y^{+}) ⟺ X^{−} ⊆ Y^{−} és X^{+} ⊇ Y^{+}. Két pár pontosan akkor összefüggő a párokon definiált értelemben, ha a posetben összefüggő. A posetben egy intervallumban levő összes elem lefogható egy éllel.

Bizonyítás. Az összefüggőségre vonatkozó állítás nyilvánvaló. Könnyen ellenőrízhető továbbá, hogy X^{−} ∩ Y^{−} ≠ ∅, X^{+} ∩ Y^{+} ≠ ∅ esetén

(X^{−}, X^{+}) ∧ (Y^{−}, Y^{+}) = (X^{−} ∩ Y^{−}, X^{+} ∪ Y^{+})
(X^{−}, X^{+}) ∨ (Y^{−}, Y^{+}) = (X^{−} ∪ Y^{−}, X^{+} ∩ Y^{+})

Tegyük fel, hogy m = (m^{−}, m^{+}) minimális és M = (M^{−}, M^{+}) maximális elemek,

(m^{−}, m^{+}) ⪯ (X^{−} ∩ Y^{−}, X^{+} ∪ X^{+}) ⪯ (M^{−}, M^{+})

Az utóbbiból M^{+} ⊆ X^{+} ∪Y^{+}, ezért vagy M^{+} ∩X^{+} ≠ ∅, vagy M^{+} ∩Y^{+} ≠ ∅. A szimmetria miatt feltehetjük, hogy M^{+} ∩ X^{+} ≠ ∅. M^{−} ⊇ X^{−} ∩ Y^{−} miatt ráadásul M^{−} ∩ X^{−} ≠ ∅, azaz M és X összefüggők. Innen M maximalitása alapján X ⪯ M. A feltétel első feléből viszont m ⪯ X adódott, tehát X ∈ [m, M]. Ugyanígy látható be, hogy ha m ⪯ (X^{−} ∩ Y^{−}, X^{+}∪X^{+}) ⪯ M akkor X ∈ [m, M] vagy Y ∈ [m, M]. Ezzel igazoltuk az erős intervallum tulajdonság teljesülését.

Az [m, M] intervallumban levő elemeket minden olyan xy él le fogja fogni, melyre x ∈ m^{−}, y ∈ M^{+}. □

Legyen most adott a P erős poseten egy p szupermoduláris függvény, azaz ha x és y összefüggő elemek, melyekre p(x) > 0, p(y) > 0, akkor

p(x ∨ y) + p(x ∧ y) ≥ p(x) + p(y)

Legyen I = {I_{i} : I_{i} = [m_{i}, M_{i}] : 1 ≤ i ≤ k} intervallumrendszer (amiben egy adott intervallum többször is szerepelhet). Legyen f(x) = |i : x ∈ I_{i}, 1 ≤ i ≤ k|, azaz az x-et fedő intervallumok száma. Mondjuk azt, hogy I fedi p-t, ha ∀x : f(x) ≥ p(x). Legyen egy adott p-re

ν(p) = max{∑_{i} p(x_{i}) : az x_{i} elemek páronként függetlenek.}

A 5.1.1 lemma szerint a Szupermoduláris Fedési Tétel következni fog az alábbi tételből:

5.1.2. Tétel. Egy P erős poseten adott p keresztezőn szupermoduláris függvényre a p-t fedő intervallumok minimális τ(p) száma ν(p)-vel egyenlő.

Megmutatjuk, hogy ez a tétel pedig következik a Szupermoduláris fedési tételből, tehát valójában ekvivalensek.

Álljon S^{−} a poset minimális, S^{+} pedig a maximális elemeinek megfelelő reprezentánsokból. Egy x minimális vagy maximális elemhez legyen ez a reprezentáns φ(x). Egy a elemhez rendeljük hozzá azt az (a^{−}, a^{+}) párt, amire

a^{−} = {φ(m) : m ⪯ a}; a^{+} = {φ(M) : M ⪰ a}

Legyen az így kapott halmazpárokból álló rendszer Q.

5.1.3. Állítás. E leképezés homeomorfizmus, azaz

(a^{−} ∩ b^{−}, a^{+} ∪ b^{+}) = ((a ∧ b)^{−}, (a ∧ b)^{+})
(a^{−} ∪ b^{−}, a^{+} ∩ b^{+}) = ((a ∨ b)^{−}, (a ∨ b)^{+})

Bizonyítás. a^{−} ∩ b^{−} = (a ∧ b)^{−} triviális, hiszen m ⪯ a és m ⪯ b ekvivalens azzal, hogy m ⪯ a ∧ b. a^{+} ∪ b^{+} = (a ∧ b)^{+} belátásához legyen először φ(M) ∈ a^{+} ∪ b^{+}, azaz M ⪰ a vagy M ⪰ b. Mivel a ∧ b ⪯ a, b, így a ∧ b ⪯ M, azaz φ(M) ∈ (a ∧ b)^{+}.

Megfordítva, legyen a ∧ b ⪯ M; m pedig legyen tetszőleges olyan minimális elem, amelyre m ⪯ a ∧ b. Ekkor m ⪯ a ∧ b ⪯ M, azaz az erős intervallum tulajdonság szerint pl. m ⪯ a ⪯ M. Ekkor φ(M) ∈ a^{+} ⊆ a^{+} ∪ b^{+}.

Teljesen ugyanígy látható be a ∨-re vonatkozó azonosság is. □

Az állításból következik, hogy Q keresztező rendszer. Legyen p′ : Q → R a következő módon definiálva: p′(X) := max{p(a) : (a^{−}, a^{+}) = X}. Könnyen belátható, hogy p′ keresztezőn szupermoduláris, továbbá hogy a Szupermoduláris Fedési Tételt a Q keresztező rendszeren a p′ függvényre alkalmazva az 5.1.2. tétel adódik.

5.1.2. Szoros elemek

Legyen I fedés. Ekkor f(x) ≥ p(x) minden x-re. Nevezzük az x elemet szorosnak, ha f(x) = p(x). (Azaz f(x) = p(x) = 0 is lehet.)

5.1.4. Lemma. Ha I fedés, x és y összefüggő szoros elemek, melyekre p(x) > 0, p(y) > 0, akkor x ∨ y és x ∧ y is szorosak.

Bizonyítás. f(x) szubmoduláris függvény. Ha ugyanis egy I_{i} intervallum x ∨ y és x ∧ y mindkettejét fedi, akkor fedi x-et és y-t is. Ha pedig pont az egyiket fedi közülük, akkor az erős intervallum tulajdonság miatt fedni fogja vagy x-et, vagy y-t. Ezt felhasználva

f(x) + f(y) = p(x) + p(y) ≤ p(x ∨ y) + p(x ∧ y) ≤ f(x ∨ y) + f(x ∧ y) ≤ f(x) + f(y) (5.1)

azaz végig egyenlőség áll. □

5.1.5. Következmény. Ha a fedés egy I_{i} intervalluma tartalmaz szoros elemet, akkor létezik benne q_{i} minimális és Q_{i} maximális szoros elem.

Kihasználva, hogy (5.1)-ben f(x) + f(y) = f(x ∨ y) + f(x ∧ y) is teljesül, könnyen látható az alábbi:

5.1.6. Lemma (Szoros fedési tulajdonság). Legyenek x és y összefüggő szoros elemek, melyekre p(x) > 0, p(y) > 0. Ha egy fedésbeli I_{i} intervallum fedi x-et vagy y-t, akkor fedi x ∨ y-t vagy x ∧ y-t is.

5.2. 0-1 értékű p fedése

Először abban a speciális esetben írjuk le az algoritmust, amikor p csak 0 és 1 értéket vehet fel. Ez annak felel meg, hogy egy k − 1 összefüggő gráfot akarunk minimális számú él hozzávételével k összefüggővé tenni.

Világos, hogy elég az olyan fedésekkel foglalkoznunk, amikben minden intervallum legfeljebb egyszer szerepel, azaz i ≠ j esetén I_{i} ≠ I_{j}.

Ha u szoros elem, és p(u) > 0, akkor p(u) = f(u) = 1. Ha u, v összefüggő szoros elemek, melyekre p(u) > 0, p(v) > 0, akkor p szupermodularitását és 0-1 értékűségét kihasználva p(x ∨ y) = p(x ∧ y) = 1 adódik. Ha most u ∈ I_{i}, v ∈ I_{j}, szoros elemek, i ≠ j, akkor a szoros fedési tulajdonság szerint mind I_{i}, mind I_{j} fedi x ∨ y és x ∧ y valamelyikét. A p(x ∨ y) = p(x ∧ y) = 1 feltételt kihasználva azt kapjuk, hogy közülük pontosan egyet fog I_{i} fedni, a másikat pedig I_{j}. Ezt az alábbi lemmában foglalhatjuk össze:

5.2.1. Lemma. Legyenek u ∈ I_{i}, v ∈ I_{j} összefüggő szoros elemek, i ≠ j. Ekkor két eset lehetséges:

• u ∨ v ∈ I_{i} − I_{j}, u ∧ v ∈ I_{j} − I_{i}, ekkor azt mondjuk, hogy v alulról függ u-tól

• u ∨ v ∈ I_{j} − I_{i}, u ∧ v ∈ I_{i} − I_{j}, ekkor pedig mondjuk azt, hogy v felülről függ u-tól.

Tehát u ∈ I_{i}, v ∈ I_{j} esetén az, hogy v alulról függ u-tól, azt jelenti, hogy m_{j} ⪯ u, v ⪯ M_{i}. Ebből adódik az alábbi egyszerű megfigyelés:

5.2.2. Állítás. Tegyük fel, hogy u, u′ ∈ I_{i}, v′, v ∈ I_{j}, i ≠ j, és u ⪯ u′, v′ ⪯ v mindannyian szoros elemek. Ekkor ha v alulról függ u-tól, akkor v′ is alulról fog függeni u′-től.

A Pushdown-Reduce algoritmus egy I fedésből kiindulva vagy megad egy ugyanannyi elemű független rendszert, vagy pedig egy eggyel kevesebb elemű fedést. Ha valamelyik I_{j} intervallum nem tartalmaz szoros elemet, akkor őt elhagyhatjuk, és készen vagyunk. Egyébként pedig t jelöli azt, hogy hanyadik fázisban járunk. Minden fázisban minden I_{j} intervallumban adott egy u_{j}^{(t)} szoros elem. Induláskor ez Q_{j}-vel, I_{j} maximális szoros elemével lesz egyenlő. Ha egy lépésben az u_{j}^{(t)} elemek páronként függetlenek (j = 1, …, k), akkor készen vagyunk: kaptunk egy optimális duális megoldást. Tegyük most fel, hogy valamely u_{j}^{(t)}-hez vannak olyan u_{i}^{(t)}-k (i ≠ j), akik alulról függnek u_{j}^{(t)}-től. Ekkor u_{j}^{(t+1)}-et a legnagyobb olyan u_{j}^{(t)}-nél kisebb I_{j}-beli szoros elemnek választjuk, aki mindezen u_{i}^{(t)}- ktől független. Ha valamely t = t^{∗}-ra és j-re nem tudunk u_{j}^{(t+1)}-et választani, akkor a Reduce(j, t^{∗}, I) meghívásával eggyel csökkentjük a fedés méretét.

Reduce(j, t^{∗}, I)-ben visszafelé haladunk a fázisok során: t = t^{∗}, ..., 1. A t. lépésben az s = t^{∗} + 1 − t jelölést használva az [m_{j_{s}}, M_{j_{s}}] intervallumot fogjuk [m_{j_{s+1}}, M_{j_{s}}]-re lecserélni úgy, hogy [m_{j_{s+1}}, M_{j_{s}}] tartalmazza az u_{j_{s+1}}^{(t)} elemet. Végül tehát [m_{j_{t^{∗}+1}}, M_{j_{t^{∗}}}] tartalmazni fogja u_{j_{t^{∗}+1}}^{(1)}-t. Belátjuk, hogy [m_{j_{t^{∗}+1}}, M_{j_{t^{∗}}}]-ban benne lesz [m_{j_{t^{∗}+1}}, M_{j_{t^{∗}+1}}] összes szoros eleme, s így ez utóbbi intervallum elhagyható lesz. Ezáltal egy eggyel kisebb fedéshez jutunk.

Algorithm Pushdown-Reduce(I) for j = 1, ..., k do

Ha I_{j} nem tartalmaz szoros elemet, akkor

megállunk a kisebb {I_{i} : i = 1, ..., j − 1, j + 1, ..., k} fedéssel u_{j}^{(1)} ← Q_{j}

for t = 1, 2, ... do

Ha az u_{i}^{(t)} elemek páronként függetlenek akkor

megállunk e maximális független rendszerrel for j = 1, ..., k do

u_{j}^{(t+1)} ← Pushdown(j, t, I)

Procedure Pushdown(j, t, I)

V ← {x : m_{j} ⪯ x ⪯ u_{j}^{(t)}, x szoros, és semmilyen i-re x nem függ alulról u_{i}^{(t)}-től} Ha V = ∅ akkor

t^{∗} ← t;

Reduce(j, t^{∗}, I)

kimenet: a maximális x ∈ V

Procedure Reduce(j, t^{∗}, I)

j_{1} ← j; for t = t^{∗}, ..., 1 do

s ← t^{∗} + 1 − t

q_{j_{s}} ← [m_{j_{s}}, M_{j_{s}}] minimális szoros eleme
j_{s+1} ← olyan l ≠ j_{s} amire m_{l} ⪯ q_{j_{s}} és u_{l}^{(t)} ⪯ M_{j_{s}}
m_{j_{s}} ← m_{j_{s+1}}

megállunk a kisebb {[m_{i}, M_{i}] : 1 ≤ i ≤ k, i ≠ j_{t^{∗}+1}} fedéssel.

5.2.1. A helyesség bizonyítása

A helyesség az alábbi lemmákból következik.

5.2.3. Lemma. Ha a Pushdown(j, t, I) lépésben V nemüres, akkor van maximális eleme.

5.2.4. Lemma. A Reduce(j, t^{∗}, I) lépésben

(i). j_{2} létezni fog.

(ii). t^{∗} = 1 esetén a kapott intervallumok valóban fedést adnak.

(iii). I′ = I − [m_{j_{1}}, M_{j_{1}}] + [m_{j_{2}}, M_{j_{1}}] szintén fedés.

5.2.5. Lemma. t^{∗} > 1 esetén Pushdown-Reduce(I′) t = 1, ..., t^{∗} − 1-re ugyanazt a kimenetet adja, mint Pushdown-Reduce(I), és a t = t^{∗} − 1 lépésnél hívja meg Reduce(j_{2}, t^{∗} − 1, I′)-t.

Ezekből következni fog az algoritmus helyessége. Tekintsük minden j-re az alábbi csökkenő sorozatot:

u_{j}^{(1)} ⪰ u_{j}^{(2)} ⪰ ... ⪰ u_{j}^{(t)} ⪰ ... ⪰ q_{j}

Ha u_{j}^{(t)} és u_{j′}^{(t)} összefüggők, akkor függjön pl. u_{j′}^{(t)} alulról u_{j}^{(t)}-től. Ekkor a Pushdown(j, t, I) lépésben u_{j}^{(t)} ∉ V, tehát ha létezik, akkor u_{j}^{(t+1)} ≺ u_{j}^{(t)}. Ebből következik, hogy az algoritmus egy idő után vagy megtalál egy független rendszert, vagy meghívja Reduce(j, t^{∗}, I)-t.

t^{∗} szerinti indukcióval bizonyítjuk, hogy minden t-re (i) j_{s+1} létezik; (ii) a módosított intervallumrendszer is fedés lesz; (iii) az s = t^{∗} lépésben [m_{j_{t^{∗}+1}}, M_{j_{t^{∗}+1}}] elhagyható lesz. t^{∗} = 1-re mindez a 5.2.4 lemmából következik, az indukiós lépést pedig a 5.2.5 lemma adja meg. 5.2.3 Bizonyítása. Legyenek x, x′ ∈ V elemek. Ekkor x és x′ összefüggőek, és belátjuk, hogy x ∨ x′ ∈ V. Ebből az állítás következni fog. Tegyük fel, hogy x ∨ x′ ∉ V. A 5.1.4. lemma szerint x ∨ x′ is szoros, és m_{j} ⪯ x ∨ x′ ⪯ u_{j}^{(t)}. Az lehet tehát csak a baj, hogy valamely i-re u_{i}^{(t)} alulról függ x ∨ x′-től. Ekkor m_{i} ⪯ x ∨ x′ és u_{i}^{(t)} ⪯ M_{j}. Az erős intervallum tulajdonság miatt m_{i} ⪯ x vagy m_{i} ⪯ x′. A szimmetria miatt feltehetjük az előbbit; ekkor u_{i}^{(t)} alulról függ x-től is, ellentmondva annak, hogy x ∈ V. □

5.2.4 Bizonyítása. (i) Ha Reduce(j, t^{∗}, I) első lépésében nincs a feltételt kielégítő l, akkor minden olyan i-re, amire u_{i}^{(1)} ⪯ M_{j}, az lesz igaz, hogy m_{i} ⪯̸ q_{j}. Tekintettel arra, hogy m_{j} ⪯ q_{j} ⪯ u_{j}^{(t)} és q_{j} szoros, adódik, hogy q_{j} ∈ V, azaz V ≠ ∅.

(ii) A t^{∗} = 1 feltételből u_{j_{2}}^{(t^{∗})} = Q_{j_{2}}. j_{2} definíciójából m_{j_{2}} ⪯ q_{j_{1}} ⪯ Q_{j_{1}} ⪯ M_{j_{1}} és m_{j_{2}} ⪯ q_{j_{2}} ⪯ Q_{j_{2}} = u_{j_{2}}^{(t^{∗})} ⪯ M_{j_{1}}, azaz [m_{j_{2}}, M_{j_{1}}] fedni fogja [m_{j_{2}}, M_{j_{2}}] és [m_{j_{1}}, M_{j_{1}}] összes szoros elemét.

Egy nem szoros x elemmel akkor lehetne baj, ha f(x) kettővel csökkene. Ez x ∈ [m_{j_{2}}, M_{j_{2}}] ∩ [m_{j_{1}}, M_{j_{1}}] lenne elképzelhető, ekkor viszont m_{j_{2}} ⪯ x ⪯ M_{j_{1}}.

(iii) Be kell látnunk, hogy I′ fed minden m_{j_{1}} ⪯ x ⪯ M_{j_{1}} elemet. Ha x nem volt szoros, akkor ez világos, mivel egy híján az összes eddig őt fedő intervallum megmaradt. j_{2} választása miatt viszont m_{j_{2}} ⪯ q_{j_{1}} ⪯ Q_{j_{1}} ⪯ M_{j_{1}}, azaz [m_{j_{2}}, M_{j_{1}}] fedi az összes szoros x ∈ [m_{j_{1}}, M_{j_{1}}]-et. □

5.2.5 Bizonyítása.

Legyen I′_{j_{1}} = [m_{j_{2}}, M_{j_{1}}]. Legyen Z_{1} azon I-beli szoros elemek halmaza, amik I′-ben nem szorosak, Z_{2} pedig legyen az I′-beli új szoros elemek halmaza. Könnyen belátható az alábbi:

5.2.6. Állítás.

Z_{1} ⊆ {x : x ∈ [m_{j_{2}}, M_{j_{1}}], x ⪰̸ m_{j_{1}}}  (5.2)
Z_{2} ⊆ {x : x ∈ [m_{j_{1}}, M_{j_{1}}], x ⪰̸ m_{j_{2}}}  (5.3)

5.2.7. Következmény. A I fedésben I_{j_{1}} szoros elemei éppen ugyanazok lesznek, mint az I′ fedésben I′_{j_{1}} szoros elemei.

Ezt a következményt használjuk ki az alábbi állításban:

5.2.8. Állítás. Tegyük fel, hogy x és y mind I-ben, mind I′-ben különböző intervallumok által fedett szoros elemek. Ekkor ha x alulról függött I-ben y-tól, akkor I′-ben is alulról fog tőle függni; ha x felülről függött I-ben y-tól, akkor I′-ben is felülről fog tőle függni.

Bizonyítás. Legyenek x ∈ I_{l}, y ∈ I_{h}. Ha h ≠ j_{1}, l ≠ j_{1}, akkor az állítás nyilvánvaló. Tegyük fel, hogy pl. h = j_{1}. Mivel x és y mindkét fedésben szoros elemek, ezért mind x ∨ y, mind x ∧ y is mindkét fedésben szorosak lesznek. I_{l} ugyanaz a két fedésben, tehát mindkettőben vagy x ∨ y-t, vagy x ∧ y-t fedi. A 5.2.7 következmény értelmében I_{j_{1}} is ugyanazt fogja fedni x ∨ y és x ∧ y közül, amelyiket I′_{j_{1}}. □

Jelöljük a Pushdown-Reduce(I′) futásából kapott értékeket u′_{i}^{(t)}-vel (u′_{j_{1}}^{(t)} az I′_{j_{1}}-beli szoros elemeket fogja jelölni).

5.2.9. Állítás. Ha t < t^{∗}, akkor u_{h}^{(t)} nem függhet I-ben alulról q_{j}-től.

Bizonyítás. Tegyük fel indirekten, hogy u_{h}^{(t)} alulról függ q_{j}-től. A 5.2.2 állítás miatt ekkor u_{h}^{(t)} alulról függ u_{j}^{(t)}-től is. Így a Pushdown(j, t, I) lépésben V üres lesz, azaz az algoritmus meghívja Reduce(j, t, I)-t, noha t < t^{∗}. □

5.2.10. Állítás. t = 1, ..., t^{∗} − 1-re u′_{i}^{(t)} = u_{i}^{(t)}, i = 1, 2, ..., k.

Bizonyítás. Indukcióval bizonyítunk. t = 1-re belátjuk, hogy minden h-ra Q_{h} szoros lesz I′-ben és Q′_{h} is szoros lesz I-ben. Ebből Q_{h} = Q′_{h} következni fog. h = j_{1}-re ez a 5.2.7. következményből adódik. h ≠ j_{1}-re tegyük fel először indirekten, hogy Q_{h} nem lesz szoros I′-ben. Ekkor Q_{h} ∈ Z_{1}, azaz (5.2) szerint u_{h}^{(1)} = Q_{h} ∈ [m_{j_{2}}, M_{j_{1}}]. Mivel q_{j_{1}} ∈ [m_{j_{2}}, M_{j_{1}}] is teljesül, ezért u_{h}^{(1)} alulról függ I-ben q_{j_{1}}-től, ellentmondásban a 5.2.9 állítással j = j_{1}-re. Ezzel beláttuk, hogy Q_{h} szoros I′-ben is, azaz Q_{h} ⪯ Q′_{h}.

Tegyük most fel, hogy Q′_{h} nem szoros I-ben, vagyis Q′_{h} ∈ Z_{2}, azaz (5.3) alapján Q′_{h} ∈ [m_{j_{1}}, M_{j_{1}}]. A 5.2.7. következmény miatt q_{j_{1}} = q′_{j_{1}}. Ezért u′_{h}^{(1)} = Q′_{h} és q′_{j_{1}} I′-ben összefüggő szoros elemek, és u′_{h}^{(1)} ⪯ M_{j_{1}}. Ebből az következik, hogy I′-ben u′_{h}^{(1)} alulról függ q′_{j_{1}}-től. Tudjuk, hogy Q_{h} ⪯ Q′_{h}-t és hogy u_{h}^{(1)} = Q_{h} ∈ I_{h} = I′_{h} szoros elem I′-ben. Az 5.2.2. állítás szerint u_{h}^{(1)} is alulról függ q′_{j_{1}}-től I′-ben. Mivel mindketten mindkét fedésben szoros elemek, az 5.2.8. állításból azt kapjuk, hogy u_{h}^{(1)} I-ben is alulról fog függni q′_{j_{1}} = q_{j_{1}}-től, ami ellentmondás. Ezzel a t = 1 esetre beláttuk az állítást.

Tegyük fel, hogy t > 1, és a t-nél kisebb értékekre beláttuk; most belátjuk t-re is (t ≤ t^{∗} − 1). Legyen V Pushdown(h, t − 1, I) futásában meghatározott halmaz; legyen V′ e halmaz Pushdown(h, t − 1, I′)-re. Belátjuk, hogy u′_{h}^{(t)} létezik, és u_{h}^{(t)} ∈ V′, u′_{h}^{(t)} ∈ V. Ebből az állítás adódik.

(I.) Tegyük fel indirekten, hogy u_{h}^{(t)} ∉ V′

(A) eset: h ≠ j_{1}. Az indukció miatt u_{i}^{(t−1)} = u′_{i}^{(t−1)}, mind I-ben, mind I′-ben szoros elemek (i = 1, …, k). Az 5.2.8. állítás alapján u_{i}^{(t−1)} pontosan akkor függ alulról u_{h}^{(t−1)}-től I-ben, amikor I′-ben. Ezért V és V′ definíciójában minden ugyanaz, kivéve a szorosságot: u_{h}^{(t)} ∉ V′ csak abban az esetben lehetséges, ha u_{h}^{(t)} ∈ Z_{1}. Így (5.2) alapján u_{h}^{(t)} ∈ [m_{j_{2}}, M_{j_{1}}]. Ezért I-ben u_{h}^{(t)} alulról függ q_{j_{1}}-től, ellentmondásban a 5.2.9. állítással.

(B) eset: h = j_{1}. u_{j_{1}}^{(t)} ∉ V′ az indukció és a 5.2.8 állítás miatt akkor lehetne, ha vagy u_{j_{1}}^{(t)} ∉ I′_{j_{1}}, vagy u_{j_{1}}^{(t)} nem szoros I′-ben, azaz u_{j_{1}}^{(t)} ∈ Z_{1}. Mindkettőnek az az akadálya, hogy u_{j_{1}}^{(t)} ⪰ q_{j_{1}} ⪰ m_{j_{2}}, m_{j_{1}}.

Tehát beláttuk, hogy minden h-ra u_{h}^{(t)} ∈ V′, azaz szoros elem I′-ben. V′ ≠ ∅ miatt következik, hogy u′_{h}^{(t)} létezik és u_{h}^{(t)} ⪯ u′_{h}^{(t)}.

(II.) Tegyük fel most, hogy u′_{h}^{(t)} ∉ V.

(A) eset: h ≠ j_{1}. Az (IA) esethez hasonlóan az lehet a baj, ha u′_{h}^{(t)} ∈ Z_{2}, azaz (5.3) miatt u′_{h}^{(t)} ∈ [m_{j_{1}}, M_{j_{1}}]. Innen a t = 1 eset bizonyításához hasonlóan adódik az ellentmondás kihasználva azt, hogy u_{h}^{(t)} ⪯ u′_{h}^{(t)} és u_{h}^{(t)} ∈ I_{h} = I′_{h} szoros elem.

(B) eset: h = j_{1}. Az (IB) esethez hasonlóan vagy u′_{j_{1}}^{(t)} ∉ I_{j_{1}}, vagy u′_{j_{1}}^{(t)} ∈ Z_{2}. Az (I). ben belátottak miatt m_{j_{1}}, m_{j_{2}} ⪯ q_{j_{1}} ⪯ u_{j_{1}}^{(t)} ⪯ u′_{j_{1}}^{(t)}, ami szintén gátja mindkét lehetőségnek. □

Ezek után a lemma állításának második fele már egyszerűen következik. Az alábbiakban V a Pushdown(j_{2}, t^{∗} − 1, I)-ben definiált halmaz, V′ pedig Pushdown(j_{2}, t^{∗} − 1, I′)-ben ugyanez. Azt állítjuk, hogy V′ = ∅.

Tegyük fel ezzel szemben, hogy V′ ≠ ∅, azaz u′_{j_{2}}^{(t^{∗})} létezik. Láttuk, hogy u′_{j_{2}}^{(t^{∗})} ∉ V csupán akkor lehetne, ha u′_{j_{2}}^{(t^{∗})} ∈ Z_{2}. Ez u′_{j_{2}}^{(t^{∗})} ⪰ m_{j_{2}} miatt lehetetlen. Tehát u′_{j_{2}}^{(t^{∗})} ∈ V, ezért u′_{j_{2}}^{(t^{∗})} ⪯ u_{j_{2}}^{(t^{∗})} ⪯ M_{j_{1}}, azaz u′_{j_{2}}^{(t^{∗})} ∈ [m_{j_{2}}, M_{j_{2}}] ∩ [m_{j_{2}}, M_{j_{1}}], de ez ellentmond annak a feltevésnek, hogy I′-ben szoros volt. □

5.3. Az általános eset

A 0 − 1 értékű esethez hasonlóan az algoritmus kiindul egy I = {I_{i} : I_{i} = [m_{i}, M_{i}] : 1 ≤ i ≤ k} fedésből, és vagy megad egy kisebb fedést, vagy ad egy tanút I minimalitására. (I ugyanazt az intervallumot többször is tartalmazhatja.) Legyen minden i = 1, …, k-ra adott egy u_{i} ∈ I_{i} szoros elem.

5.3.1. Állítás. Ha minden i, j-re u_{i} és u_{j} vagy függetlenek, vagy u_{i} = u_{j}, akkor ezen {u_{i}} elemek optimális duális megoldást adnak.

Bizonyítás. Azt kell belátni, hogy ha valamely y-ra létezik olyan i, amire y = u_{i}, akkor pontosan p(y) darab ilyen i létezik. Mivel y = u_{i} szoros, így pontosan p(y) darab j-re lesz y ∈ I_{j}. A feltétel szerint egy ilyen j-re u_{i} és u_{j} vagy független, vagy u_{i} = u_{j}. Ám függetlenek nem lehetnek, hiszen az I_{j} intervallum mindkettejüket fedi. □

Lényeges különbség a 0-1 esethez képest abban lesz, hogy az I_{i} és I_{j} intervallumoknak lehet közös szoros elemük, sőt, egy u_{i} I_{i}-n kívül más intervallumokban is szerepelhet. Legyenek x ∈ I_{i}, y ∈ I_{j} összefüggő szoros elemek. Értsük x és y (i, j)-szerinti viszonya alatt azt, hogy az x ∨ y és x ∧ y elemek közül melyeket tartalmazza I_{i} és melyeket I_{j}. A 5.2.1 lemmában leírt esetekben mondjuk azt, hogy x és y regulárisan függő pár (i, j)- szerint. Egyébként egy összefüggő párra mondjuk azt, hogy nemregulárisan függenek. A 0-1 esetben ilyen nem volt: abból, hogy x∨y ∈ I_{i}, következett, hogy x∨y ∉ I_{j}. Ez általában már nem lesz igaz, a szoros fedési tulajdonság alapján összesen annyit mondhatunk, hogy mind I_{i}, mind I_{j} az x ∨ y és x ∧ y elemek közül legalább egyet tartalmaz.

A nemreguláris függési viszonyok közül egyet szükséges még megneveznünk: ha x ∧ y ∈ I_{i} ∩ I_{j}, akkor mondjuk azt, hogy x és y (i, j)-szerint lent kapcsolt pár. Ha az (i, j) szerinti viszonyban egyértelmű, hogy mi az i és a j (pl. u_{i} és u_{j} esetén), akkor ezt nem fogjuk külön mondani. Megjegyezzük, hogy az 5.2.2. állítás az általános esetben is igaz marad.

Az algoritmus lényegét a 0-1 eset kis módosításával kapott Pushdown-Reduce adja. Ezt addig tudjuk alkalmazni, amíg vannak regulárisan függő u_{i}^{(t)}, u_{j}^{(t)} párok. Elképzelhető azonban, hogy a Pushdown-Reduce végén még marad olyan u_{i}^{(t)} és u_{j}^{(t)}, akik nem regulárisan függenek.

Szerencsére azonban ez esetben már igaz lesz az, hogy a fedés minimális. A kapott u_{i}^{(t)}-kből kiindulva az egyszerű, mohó PushToMin szubrutinnal meg fogunk találni egy tanút.

5.3.1. Pushdown-Reduce az általános esetben

Algorithm Pushdown-Reduce(I)

for j = 1, ..., k do

Ha I_{j} nem tartalmaz szoros elemet, akkor

megállunk a kisebb {I_{i} : i = 1, ..., j − 1, j + 1, ..., k} fedéssel u_{j}^{(1)} ← Q_{j}

for t = 1, 2, ... do

Ha az u_{i}^{(t)} elemek páronként vagy függetlenek vagy nem regulárisan függnek, akkor

PushToMin({u_{i}^{(t)}}) for j = 1, ..., k do

u_{j}^{(t+1)} ← Pushdown(j, t, I)

Az algoritmusban Pushdown(j, t, I) és Reduce(j, t^{∗}, I) szó szerint ugyanaz lesz, mint a 0-1 esetben. A helyesség igazolásához is ugyanazokat a lemmákat látjuk be, mint a 0-1 esetben, bizonyításaik természetesen módosulni fognak.

5.3.2. Lemma. Ha a Pushdown(j, t, I) lépésben V nemüres, akkor van maximális eleme.

5.3.3. Lemma. A Reduce(j, t^{∗}, I) lépésben

(i). j_{2} létezni fog.

(ii). t^{∗} = 1 esetén a kapott intervallumok valóban fedést adnak.

(iii). I′ = I − [m_{j_{1}}, M_{j_{1}}] + [m_{j_{2}}, M_{j_{1}}] szintén fedés.

5.3.4. Lemma. t^{∗} > 1 esetén Pushdown-Reduce(I′) t = 1, ..., t^{∗} − 1-re ugyanazt a kimenetet adja, mint Pushdown-Reduce(I), és a t = t^{∗} − 1 lépésnél hívja meg Reduce(j_{2}, t^{∗} − 1, I′)-t.

5.3.2 Bizonyítása. A 0-1 esetnél most kissé bonyolultabb feltételünk lesz arra, hogy mikor függ u_{i}^{(t)} alulról x-től m_{j} ⪯ x ⪯ u_{j}^{(t)} esetén.

5.3.5. Állítás. Tegyük fel, hogy u_{i}^{(t)} alulról függ u_{j}^{(t)}-től, és x szoros elem, m_{j} ⪯ x ⪯ u_{j}^{(t)}.

(i) u_{i}^{(t)} pontosan akkor függ alulról x-től, ha m_{i} ⪯ x ⪯̸ M_{i}. (ii) u_{i}^{(t)} pontosan akkor nem függ alulról x-től, ha vagy m_{i} ⪯̸ x, vagy m_{i} ⪯ x ⪯ M_{i}.

V maximális elemének létezéséhez ismét azt kell belátni, hogy ha x, x′ ∈ V, akkor x ∨ x′ ∈ V. Tegyük fel, hogy x ∨ x′ ∉ V. Az 5.1.4. lemma szerint x ∨ x′ is szoros, és m_{j} ⪯ x ∨ x′ ⪯ u_{j}^{(t)}. Az lehet tehát csak a baj, hogy valamely i-re u_{i}^{(t)} alulról függ u_{j}^{(t)}-től és x ∨ x′-től is. Az 5.3.5. állítás szerint ekkor m_{i} ⪯ x ∨ x′ ⪯̸ M_{i}. Az erős intervallum tulajdonság miatt m_{i} ⪯ x vagy m_{i} ⪯ x′. A szimmetria miatt feltehetjük, hogy m_{i} ⪯ x. Ekkor u_{i}^{(t)} nem függhet alulról x-től, tehát a 5.3.5 állítás miatt m_{i} ⪯ x ⪯ M_{i}, vagyis x ∈ I_{i}. A szoros fedési tulajdonság miatt vagy x ∨ x′ ∈ I_{i}, vagy x ∧ x′ ∈ I_{i}. Az előbbit kizártuk, tehát m_{i} ⪯ x ∧ x′ ⪯ x′. Ekkor x-hez hasonlóan x′ ∈ I_{i} lesz. Ha azonban x, x′ ∈ I_{i}, akkor x ∨ x′ ∈ I_{i}, ami ellentmondás. □ 5.3.3 Bizonyítása. (i) A Pushdown(j_{1}, t^{∗}, I) lépésben q_{j_{1}} ∉ V. Mivel m_{j_{1}} ⪯ q_{j_{1}} ⪯ u_{j_{1}}^{(t)} szoros elem, ezért kell legyen olyan l, akire u_{l}^{(t^{∗})} alulról függ u_{j_{1}}^{(t^{∗})}-tól. Ez az l megfelelő lesz. (ii) és (iii) bizonyítása ugyanaz, mint a 0-1 esetben. □ 5.3.4 Bizonyítása. Világos, hogy azon I-beli szoros elemek halmaza, amik I′-ben nem szorosak, és az I′-beli új szoros elemek halmaza ugyanaz a Z_{1} és Z_{2}, ami a 0-1 esetben volt (ld. (5.2),(5.3) ). Igaz lesz a 5.2.7. következmény is. A 5.2.8. állításnak megfelelően igaz lesz az alábbi, szó szerint ugyanazzal a bizonyítással.

5.3.6. Állítás. Ha x ∈ I_{h} és y ∈ I_{l} I-ben és I′-ben is szoros elemek, akkor x és y viszonya (h, l) szerint ugyanaz I-ben és I′-ben.

A 0-1 esethez hasonlóan jelöljük a Pushdown-Reduce(I′) futásából kapott értékeket u′_{i}^{(t)}-vel (u′_{j_{1}}^{(t)} az I′_{j_{1}}-beli szoros elemeket fogja jelölni).

Legyen most j és t ≤ t^{∗} tetszőleges, és x ∈ I_{j} szoros elem, melyre x ⪯̸ u_{j}^{(t)}. Legyen t_{0} a legnagyobb olyan index, amelyre x ⪯ u_{j}^{(t_{0})}. Ez létezni fog, mivel x ⪯ Q_{j} = u_{j}^{(1)}, hiszen x szoros. A Pushdown(j_{1}, t_{0}, I) lépésben x ∉ V, kell legyen tehát olyan d, hogy e lépésben u_{d}^{(t)} alulról függött x-től. Ekkor mondjuk azt, hogy u_{j}^{(t)} esetén x átugrásának u_{d}^{(t_{0})} az oka. (Egy átugrásnak persze több oka is lehet.)

5.3.7. Állítás. u_{j}^{(t)} esetén legyen x ∈ I_{j} átugrásának u_{d}^{(t_{0})} az oka.

(i) m_{d} ⪯ x ⪯̸ M_{d}, u_{d}^{(t_{0})} ⪯ M_{j}.

(ii) Ha m_{d} ⪯ u_{j}^{(t)}, akkor u_{j}^{(t)} ⪯ M_{d}

(iii) Ha x = u_{j}^{(t)} ∨ z, akkor m_{d} ⪯ z.

Bizonyítás. (i) Az első fele az 5.3.5. állításból következik, az utóbbi pedig abból, hogy u_{d}^{(t_{0})} alulról függött u_{j}^{(t_{0})}-tól.

(ii) Ekkor m_{d} ⪯ u_{j}^{(t)} ⪯ u_{j}^{(t_{0})}, és innen u_{j}^{(t_{0})} ⪯ M_{d} az 5.3.5. állítás szerint.

(iii) m_{d} ⪯ x, tehát az erős intervallum tulajdonság szerint vagy m_{d} ⪯ u_{j}^{(t)}, vagy m_{d} ⪯ z. Az utóbbi esetben készen vagyunk. Tegyük fel, hogy m_{d} ⪯ u_{j}^{(t)}. A (ii) pont szerint ekkor u_{j}^{(t)} ∈ I_{d}. A szoros fedési tulajdonságot használva x = u_{j}^{(t)} ∨ z ∈ I_{d} vagy u_{j}^{(t)} ∧ z ∈ I_{d}. Az első alternatívát kizártuk az (i) pontban, tehát u_{j}^{(t)} ∧ z ∈ I_{d}, azaz m_{d} ⪯ u_{j}^{(t)} ∧ z ⪯ z. □

Az 5.2.9. állítás helyett az alábbi lesz igaz:

5.3.8. Lemma. Ha t ≤ t^{∗}-ra q_{j} és u_{h}^{(t)} összefüggőek, akkor q_{j} ⪯ u_{h}^{(t)}.

Bizonyítás. Tegyük fel, hogy u = u_{h}^{(t)} és q = q_{j} összefüggőek, ám q ⪯̸ u. Legyen u_{h}^{(t)} az az ellenpélda, amire t minimális. Legyen s = u ∨ q, w = u ∧ q. A szoros fedési tulajdonság miatt vagy s ∈ I_{j}, vagy w ∈ I_{j}. Az utóbbi esetben - mivel w ∈ I_{j} pontos és I_{j} minimális pontos eleme q - azt kapjuk, hogy q ⪯ w ⪯ u, noha ennek feltettük az ellenkezőjét. Tehát s ∈ I_{j}, azaz s ⪯ M_{j}.

Szintén a szoros fedési tulajdonság miatt s ∈ I_{h} vagy w ∈ I_{h}. Tegyük fel, hogy s ∉ I_{h}. Ekkor w ∈ I_{h}, ahonnan s ∈ I_{j} és w ∉ I_{j} miatt u alulról függ q-tól. Így Pushdown(j, t, I) futásakor V üres lesz, azaz az algoritmus meghívja Reduce(j, t^{∗}, I)-t, noha t < t^{∗}, s ez ellentmondás.

Az a lehetőség maradt hát, hogy s ∈ I_{j}∩I_{h}. Mivel feltettük, hogy q ⪯̸ u, ezért s = q∨u ⪯̸ u. Legyen u_{d}^{(t_{0})} annak az oka, hogy u átugrotta s-et. A 5.3.7 állítás (iii) pontja alapján (x = s, z = q, j = h szereposztással) m_{d} ⪯ q. Mivel m_{d} ⪯ u_{d}^{(t_{0})} ⪯ M_{h} és m_{d} ⪯ q ⪯ M_{h}, ezért u_{d}^{(t_{0})} és q összefüggőek. t minimális választása és t_{0} < t miatt q ⪯ u_{d}^{(t_{0})} ⪯ M_{d}. Innen azt kapjuk, hogy q ∈ I_{d}.

A szoros fedési tulajdonság miatt tehát vagy s ∈ I_{d}, vagy w ∈ I_{d}. A 5.3.7 állítás (i) pontja miatt s ∉ I_{d}, tehát w ∈ I_{d}, azaz m_{d} ⪯ w ⪯ u. Ekkor a 5.3.7 állítás (ii) pontja szerint u ∈ I_{d}. Ha viszont q, u ∈ I_{d}, akkor s = u ∨ q ∈ I_{d}, ismét csak ellentmondás. □

Ennek párjaként I′-re az alábbi fog teljesülni:

5.3.9. Lemma. Tegyük fel, hogy t ≤ t^{∗}-ra és h ≠ j-re u′_{h}^{(t)} létezik, q′_{j} és u′_{h}^{(t)} összefüggő elemek, és q′_{j} ⪯̸ u′_{h}^{(t)}. Ekkor u′_{h}^{(t)} alulról függ q′_{j}-től.

Bizonyítás. Tegyük fel, hogy u = u′_{h}^{(t)} és q = q′_{j} összefüggőek. Legyen u′_{h}^{(t)} az az ellenpélda, amire t minimális.

5.3.10. Állítás. Ha t_{0} < t, és valamely d-re u′_{d}^{(t_{0})} és q′_{j} összefüggőek, akkor q′_{j} ⪯ u′_{d}^{(t_{0})}

Bizonyítás. Tegyük fel, hogy u′_{d}^{(t_{0})} és q′_{j} összefüggőek, ám q′_{j} ⪯̸ u′_{d}^{(t_{0})}. Ekkor t minimalitása miatt u′_{d}^{(t_{0})} alulról függ q′_{j}-től. Emiatt Pushdown(j, t_{0}, I′) futásakor V′ üres lesz, azaz az algoritmus meghívja Reduce(j, t_{0}, I′)-t, noha t_{0} < t és u′_{h}^{(t)} létezett, tehát Pushdown-Reduce(I′) nem érhet véget a t_{0}. lépésben. □

A 5.3.8 lemma bizonyításának nyomán azt kapjuk, hogy vagy u alulról függ q-tól - ez esetben készen vagyunk - vagy s ∈ I_{j} ∩ I_{h}. Innentől a bizonyítás szó szerint ugyanaz lesz, mint a 5.3.8. lemma esetében, azzal az egy különbséggel, hogy q ⪯ u′_{d}^{(t_{0})} ⪯ M_{d} a 5.3.10. állításnak lesz a következménye. □

5.3.4 bizonyításában a lényegi állítás is ugyanaz lesz, mint a 0-1 esetben:

5.3.11. Állítás. t = 1, …, t^{∗} − 1-re u′_{i}^{(t)} = u_{i}^{(t)}, i = 1, 2, …, k.

Bizonyítás. Indukcióval bizonyítunk. t = 1-re belátjuk, hogy minden h-ra Q_{h} szoros lesz I′-ben és Q′_{h} is szoros lesz I-ben. Ebből Q_{h} = Q′_{h} következni fog. h = j_{1}-re az 5.2.7. állításból adódik. h ≠ j_{1}-re tegyük fel először indirekten, hogy Q_{h} nem lesz szoros I′-ben. Ekkor Q_{h} ∈ Z_{1}, azaz (5.2) szerint u_{h}^{(1)} = Q_{h} ∈ [m_{j_{2}}, M_{j_{1}}]. Teljesül továbbá q_{j_{1}} ∈ [m_{j_{2}}, M_{j_{1}}] is, tehát q_{j_{1}} és u_{h}^{(1)} összefüggőek. (5.2) miatt m_{j_{1}} ⪯̸ u_{h}^{(1)}, és m_{j_{1}} ⪯ q_{j_{1}} ahonnan q_{j_{1}} ⪯̸ u_{h}^{(1)} adódik. Ekkor a 5.3.8. lemmát j = j_{1}-re alkalmazva I-ben u_{h}^{(1)} független q_{j_{1}}-től, ami ellentmondás. Beláttuk, hogy Q_{h} szoros I′-ben, tehát Q′_{h} létezik és Q_{h} ⪯ Q′_{h}.

Tegyük most fel, hogy Q′_{h} nem szoros I-ben. Ekkor Q′_{h} ∈ Z_{2}, azaz (5.3) alapján Q′_{h} ∈ [m_{j_{1}}, M_{j_{1}}]. Másrészt az 5.2.7. állítás miatt q_{j_{1}} = q′_{j_{1}}. Q′_{h}, q′_{j_{1}} ∈ I_{j_{1}}, tehát u′_{h}^{(1)} = Q′_{h} és q′_{j_{1}} I′-ben összefüggő szoros elemek. Azonban m_{j_{2}} ⪯ q′_{j_{1}} és m_{j_{2}} ⪯̸ Q′_{h} = u′_{h}^{(1)} miatt q′_{j_{1}} ⪯̸ u′_{h}^{(1)}. Ebből 5.3.9 lemmát alkalmazva azt kapjuk, hogy I′-ben u′_{h}^{(1)} alulról q′_{j_{1}}-től. Kihasználva a már belátott u_{h}^{(1)} ⪯ u′_{h}^{(1)}-et és azt, hogy u_{h}^{(1)} ∈ I_{h} = I′_{h} szoros elem, a 5.2.2. állításból adódik, hogy u_{h}^{(1)} is alulról függ q′_{j_{1}}-től I′-ben. A 5.3.6 állításból ekkor u_{h}^{(1)} I-ben is alulról fog függni q′_{j_{1}} = q_{j_{1}}-től, ami ellentmondás. Ezzel a t = 1 esetet beláttuk.

t > 1-re legyen V a Pushdown(h, t − 1, I) futásában meghatározott halmaz; legyen V′ e halmaz Pushdown(h, t − 1, I′)-re. Belátjuk, hogy u′_{h}^{(t)} létezik, és u_{h}^{(t)} ∈ V′, u′_{h}^{(t)} ∈ V.

(I) Tegyük fel elsőként, hogy u_{h}^{(t)} ∉ V′

(A) eset: h ≠ j_{1}. Az 5.3.6. állítás miatt csak abból lehet a baj, ha u_{h}^{(t)} ∈ Z_{1}. Ekkor azonban (5.2) miatt m_{j_{1}} ⪯̸ u_{h}^{(t)}, azaz q_{j_{1}} ⪯̸ u_{h}^{(t)}. q_{j_{1}} és u_{h}^{(t)} összefüggőek, mivel m_{j_{2}} mindkettejüknél kisebb, M_{j_{1}} pedig mindkettejüknél nagyobb. Azonban az 5.3.8 lemma miatt u_{h}^{(t)} és q_{j_{1}} függetlenek, s ez ellentmondás.

(B) eset: h = j_{1}. A bizonyítás ugyanaz, mint a 0-1 esetben.

Innen már azt is tudjuk, hogy u′_{h}^{(t)} létezik, sőt, u_{h}^{(t)} ⪯ u′_{h}^{(t)}.

(II) Tegyük most fel, hogy u′_{h}^{(t)} ∉ V.

(A) eset: h ≠ j_{1}. Az (IA) esethez hasonlóan ekkor az lehet a baj, ha u′_{h}^{(t)} ∈ Z_{2}, azaz (5.3) miatt u′_{h}^{(t)}, q_{j_{1}} ∈ I_{j_{1}}. Innen ugyanúgy juthatunk ellentmondásra, mint a t = 1 esetben, felhasználva hogy u_{h}^{(t)} ⪯ u′_{h}^{(t)}, és u_{h}^{(t)} ∈ I_{h} = I′_{h} mindkét fedésben szoros elem.

(B) eset: h = j_{1}. Szintén megegyezik a 0-1 esettel. □

Annak bizonyítására, hogy Pushdown-Reduce(I′) a t = t^{∗} − 1 lépésnél hívja meg Reduce(j_{2})-t, szintén szó szerint elismételhető, amit a 0-1 esetben leírtunk. □

5.3.2. A PushToMin szubrutin

A PushToMin algoritmus a t^{∗} időpontban kerül meghívásra, bemenete minden i-re egy u_{i} = u_{i}^{(t^{∗})} ∈ I_{i} szoros elem, méghozzá úgy, hogy u_{i} és u_{j} vagy függetlenek, vagy (i, j) szerint nem regulárisan függőek.

Legyenek u_{i_{1}}, …, u_{i_{l}} tetszőleges elemek. Vegyük őket valamilyen sorrendben és zárójelezéssel, és írjunk közéjük ∧ jeleket. Nevezzük ezt legális zárójelezésnek, ha egy értelmes műveletsort definiál, azaz ebben a sorrendben és zárójelezéssel sorra végre tudjuk hajtani a ∧ műveleteket. (Minden ∧ végrehajtásakor a két tag összefüggő.) Egy legális zárójelezés esetén a végeredményt jelöljük ∧{u_{i_{1}}, …, u_{i_{l}}}-lel és és nevezzük u_{i_{1}}, …, u_{i_{l}} sormetszetének. Ha nincs legális zárójelezés, akkor a sormetszet nem létezik. Az alábbi lemma szerint viszont ha a van legális zárójelezés, akkor a sormetszet jóldefiniált lesz.

5.3.12. Lemma. Az u_{i_{1}}, …, u_{i_{l}} elemek minden legális zárójelezésére ugyanaz lesz az eredmény.

Bizonyítás. Tegyük fel, hogy két különböző legális zárójelezéssel két különböző végeredmény adódott, z és z′. Mindenesetre z′ ⪯ u_{i_{1}}, …, u_{i_{l}}. Ezért indukcióval látható, hogy a z kiszámítása során minden zárójelben a kiszámított érték legalább z′. (Ha ugyanis valamely y, y′ összefüggő elemekre z′ ⪯ y, z′ ⪯ y′, akkor z′ ⪯ y ∧ y′.) Azt kaptuk tehát, hogy z′ ⪯ z, és hasonlóan z ⪯ z′, vagyis z = z′. □

Egy ∧H sormetszetet nevezzünk jónak, ha minden u_{i} ∈ H-ra ∧H ∈ I_{i}. Mondjuk azt, hogy egy ∧H jó sormetszet legjobb, ha H tartalmazásra nézve maximális a jó sormetszetek között.

Megjegyzés Minden i-re az egyelemű ∧{u_{i}} = u_{i} sormetszet jó lesz.

A PushToMin algoritmus az alábbi tételen fog alapulni:

5.3.13. Tétel. (a) Bármely két különböző legjobb sormetszet független. (b) Ha ∧H és ∧L sormetszetek, L ⊂ H, akkor létezik olyan u_{i} ∈ H − L, hogy ∧(L + u_{i}) is sormetszet.

Ebből következik, hogy azok a halmazok, melyek a legjobb sormetszeteket adják, az {u_{1}, …, u_{k}} halmaz egy partícióját alkotják. A (b) rész szerint a legjobb sormetszetek mohón megtalálhatóak, elemek egyenkénti hozzávételével. Az alábbi PushToMin algoritmus tehát optimális duális megoldást ad: minden i-re u_{i}-t cseréljük le arra az egyértelmű legjobb ∧H sormetszetre, melyre u_{i} ∈ H. A tétel belátásához némi előkészületre lesz szükségünk.

5.3.14. Állítás. Ha M maximális elem, a ∧Z sormetszet létezik és ∧Z ⪯ M, akkor van olyan u_{i} ∈ Z, amelyre u_{i} ⪯ M.

Bizonyítás. Tegyük fel, hogy ∧Z olyan ellenpélda, melyre |Z| minimális. |Z| = 1 nem lehet, tehát ∧Z = (∧K) ∧ (∧K′) alakban áll elő. Az erős intervallum tulajdonság miatt vagy ∧K ⪯ M, vagy ∧K′ ⪯ M. Tegyük fel, hogy ∧K ⪯ M. |Z| minimalitása miatt van olyan u_{i} ∈ K ⊆ Z, melyre u_{i} ⪯ M. □

5.3.15. Lemma. Legyen ∧Z sormetszet, Z = X ∪ Y, X, Y ≠ ∅, X ∩ Y = ∅. Ekkor van olyan u_{i} ∈ X és olyan u_{j} ∈ Y, amelyek összefüggőek.

Bizonyítás. Legyen T ⊂ Z olyan, hogy ∧T létezik, és |T | minimális arra a tulajdonságra nézve, hogy T ∩ X ≠ ∅ és T ∩ Y ≠ ∅. Ekkor világos, hogy ∧T = (∧K) ∧ (∧K′) formában áll elő, ahol K ⊆ X, K′ ⊆ Y.

Legyen M olyan maximális elem, melyre (∧K) ∨ (∧K′) ⪯ M. Az előző állítás szerint létezik u_{i} ∈ K ⊆ X és u_{j} ∈ K′ ⊆ Y, melyekre u_{i} ⪯ M és u_{j} ⪯ M. Mivel ∧T közös alsó korlátjuk volt, ezért u_{i} és u_{j} összefüggőek lesznek. □

5.3.16. Lemma. Egy ∧Z sormetszetre ekvivalens az alábbi két állítás: (i) ∧Z jó sormetszet (ii) bármely u_{i}, u_{j} ∈ Z-re u_{i} és u_{j} vagy függetlenek, vagy lent kapcsoltak, azaz u_{i} ∧ u_{j} ∈ I_{i} ∩ I_{j}.

Bizonyítás. Az (i)⇒(ii) irány abból következik, hogy ∧Z jó sormetszet, tehát ∧Z ∈ I_{i} ∩ I_{j}. Innen u_{i} ∧ u_{j} ⪰ ∧Z ⪰ m_{i}, m_{j}. A (ii)⇒(i) irány az alábbi állításból fog következni a Z = T esetben.

5.3.17. Állítás. Tegyük fel, hogy teljesül a (ii) feltétel, létezik a ∧T sormetszet, ∧T ⪯ M_{i}, továbbá létezik m, amelyre m ⪯ ∧T, m ⪯ u_{i}. Ekkor ∧T ∈ I_{i}.

Bizonyítás. Tegyük fel, hogy nem igaz az állítás, és legyen T olyan ellenpélda, akire |T | minimális. Ha |T | = 1, akkor T = {u_{i}} nem lehet. Egyébként m ⪯ ∧T ⪯ M_{i}, m ⪯ u_{i} ⪯ M_{i} miatt ∧T és u_{i} összefüggőek. A lemma feltétele szerint ezért lent kapcsoltak, azaz (∧T) ∧ u_{i} ∈ I_{i}. Ekkor azonban m_{i} ⪯ ∧T ⪯ M_{i}.

Feltehetjük tehát, hogy |T | ≥ 2. Legyen ∧T = (∧K) ∧ (∧K′). Az erős intervallum tulajdonság miatt vagy ∧K ⪯ M_{i}, vagy ∧K′ ⪯ M_{i}. A szimmetria révén feltehetjük, hogy ∧K ⪯ M_{i}. |T | minimális választása miatt ∧K ∈ I_{i}.

A szoros fedési tulajdonság szerint vagy ∧T = (∧K)∧(∧K′) ∈ I_{i}, vagy (∧K)∨(∧K′) ∈ I_{i}. Az előbbi eset ellentmond T választásának. Az utóbbi esetben ∧K′ ⪯ M_{i}. Ismét |T | minimális választása miatt ∧K′ ∈ I_{i}. Azonban ha ∧K, ∧K′ ∈ I_{i}, akkor ∧T = (∧K) ∧ (∧K′) ∈ I_{i} ismét ellentétben T választásával. □

□

5.3.18. Lemma. Tegyük fel, hogy az s szoros elem az alábbi tulajdonsággal rendelkezik:

minden l-re, amennyiben m_{l} ⪯ s, továbbá u_{l} és s összefüggőek, akkor s ∈ I_{l}  (5.4)

Ekkor minden olyan i-re, amelyre s ∈ I_{i}, teljesülni fog s ⪯ u_{i}.

Bizonyítás. Tegyük fel indirekten, hogy létezik olyan u_{i}, melyre s ∈ I_{i}, ám s ⪯̸ u_{i}. Legyen u_{d}^{(t)} az u_{i} s alá nyomásának az oka. Ekkor a 5.3.7. állítás (i) pontja szerint m_{d} ⪯ s ⪯̸ M_{d}, és m_{d} ⪯ s, u_{d} ⪯ M_{i} miatt u_{d} és s összefüggőek. Ekkor l = d megsérti az (5.4) tulajdonságot. □

5.3.19. Lemma. Tegyük fel, hogy ∧Z legjobb sormetszet, u_{l} ∉ Z, és m_{l} ⪯ ∧Z. Ekkor ∧Z és u_{l} függetlenek.

Bizonyítás. Azt fogjuk belátni, hogy s = ∧Z kielégíti az (5.4) feltételt. Ha u_{l} ∈ Z, akkor ∧Z ∈ I_{l}, mivel ∧Z jó sormetszet. Azt az esetet kell vizsgálnunk, amikor u_{l} ∉ Z, u_{l} és ∧Z összefüggőek, valamint m_{l} ⪯ ∧Z.

Legyen Z′ = Z +u_{l}. ∧Z′ létezni fog: vegyük ∧Z egy legális zárójelezését, és ennek írjuk a végére u_{l}-et. Ez Z′ egy legális zárójelezése lesz, mivel ∧Z és u_{l} összefüggőek. Ha minden u_{i}, u_{j} ∈ Z′-re teljesülne, hogy u_{i} és u_{j} vagy lent kapcsoltak, vagy függetlenek, akkor a 5.3.16 lemma szerint ∧Z′ egy ∧Z-nél bővebb jó sormetszet lenne.

Bármely u_{i}, u_{j} ∈ Z-re ∧Z jó volta miatt u_{i} és u_{j} lent kapcsoltak vagy függetlenek. Tehát kell legyen olyan u_{i} ∈ Z, hogy u_{i} és u_{l} összefüggőek, ám nem lent kapcsoltak. A Pushtomin szubrutin kezdeti feltétele miatt u_{i} és u_{l} nem regulárisan összefüggők, tehát vagy u_{i}∨u_{l} ∈ I_{i}∩I_{l}, vagy u_{i}∧u_{l} ∈ I_{i}∩I_{l}. Az utóbbi esetben lent kapcsoltak lennének, tehát az előbbi teljesül. Ezért u_{i} ⪯ u_{i} ∨ u_{l} ⪯ M_{l}. Azt kaptuk tehát, hogy m_{l} ⪯ ∧Z ⪯ u_{i} ⪯ M_{l}, vagyis ∧Z ∈ I_{l}.

Beláttuk hát, hogy ∧Z teljesíti a (5.4) tulajdonságot. Az 5.3.18 lemma szerint ∧Z ∈ I_{l} következtében ∧Z ⪯ u_{l}. Ekkor ∧Z′ = ∧Z és ∧Z′ egy ∧Z-nél bővebb jó sormetszet, ellentétben azzal, hogy Z legjobb volt. Ebből az következik, hogy nincs olyan l, melyre u_{l} ∉ Z, ∧Z és u_{l} összefüggőek, valamint m_{l} ⪯ ∧Z. Ez pedig éppen a lemma állítása volt. □

5.3.13 Bizonyítása. A (b) rész a 5.3.15. lemma következménye az X = L, Y = H − L partícióra. Eszerint léteznek u_{j} ∈ L, u_{i} ∈ H −L összefüggő elemek. ∧L-nek és u_{i}-nek tehát ∧H közös alsó, u_{i} ∨ u_{j} közös felső korlátja. Ezért ∧(L + u_{i}) sormetszet létezni fog.

Az (a) részhez először tegyük fel, hogy ∧K és ∧K′ összefüggő legjobb sormetszetek, K ≠ K′. Vizsgáljuk azt az esetet, amikor rendezve vannak, pl. ∧K ⪯ ∧K′. Tekintsük a ∧(K ∪ K′) = ∧K sormetszetet az X = K − K′, Y = K′ partícióval. X ≠ ∅, mivel K ⊈ K′. Alkalmazhatjuk hát az 5.3.15 lemmát, ami szerint van olyan u_{i} ∈ X, u_{j} ∈ Y, melyre u_{i} és u_{j} összefüggőek. Ekkor u_{i} ∉ K′, m_{i} ⪯ ∧K ⪯ ∧K′ és ∧K′ ⪯ u_{i} ∨u_{j}, tehát u_{i} és ∧K′ összefüggőek. Ez azonban ellentmond az 5.3.19 lemmának. A továbbiakban feltesszük tehát, hogy ∧K és ∧K′ nincsenek rendezve.

A szoros fedési tulajdonság szerint minden u_{i} ∈ K ∪ K′-re vagy (∧K) ∧ (∧K′) ∈ I_{i}, vagy s = (∧K) ∨ (∧K′) ∈ I_{i}.

Legyen B azon u_{i}-k halmaza, melyekre s ∈ I_{i}. B ≠ ∅, mivel ha üres halmaz volna, akkor (∧K) ∧ (∧K′) is jó sormetszet lenne, ami ellentmond K és K′ legjobb voltának.

Legyen B_{0} = K ∩ K′. Nyilvánvaló, hogy B_{0} ⊆ B. Legyen B_{1} = K ∩ B, B_{2} = K′ ∩ B, C_{1} = K − B, C_{2} = K′ − B.

5.3.20. Állítás. Ha u_{i} ∈ C_{1}, akkor tetszőleges x-re ∧K′ ⪯ x esetén x és u_{i} függetlenek. Hasonlóan, ha u_{i} ∈ C_{2}, akkor ∧K ⪯ x esetén x és u_{i} függetlenek.

Bizonyítás. A szimmetria miatt elég a C_{1}-re vonatkozó állítást belátni. ∧K′-nek és u_{i}- nek van közös alsó korlátja: (∧K) ∧ (∧K′). Ha (∧K′) ⪯ x és u_{i} összefüggők volnának, akkor x ∨ u_{i} közös felső korlát lenne. Tehát ∧K′ és u_{i} összefüggőek, noha u_{i} ∈ C_{1} miatt m_{i} ⪯ (∧K) ∧ (∧K′) ⪯ ∧K′, u_{i} ∉ K′, vagyis a 5.3.19 lemma miatt függetlennek kellene lenniük. □

5.3.21. Lemma. Ha u_{i} ∈ B, akkor s ⪯ u_{i}.

Bizonyítás. Azt kell belátni, hogy s-re teljesül az (5.4) feltétel. Ekkor az állítás az 5.3.18 lemmából adódik. Legyen tehát l olyan, hogy m_{l} ⪯ s, valamint s és u_{l} összefüggőek. Azt kell belátni, hogy s ∈ I_{l}.

s = (∧K) ∨ (∧K′), tehát az erős intervallum tulajdonság miatt m_{l} ⪯ ∧K vagy m_{l} ⪯ ∧K′. A szimmetria miatt feltehetjük az előbbit. Ekkor ∧K legjobb sormetszet, m_{l} ⪯ ∧K, valamint ∧K és u_{l} összefüggőek, mivel m_{l} közös alsó, s ∨ u_{l} pedig közös felső korlát. Az 5.3.19. lemma szerint ez csak úgy lehet, ha u_{l} ∈ K. K = B_{1} ∪ C_{1}, tehát u_{l} e két halmaz valamelyikébe esik. Ha u_{l} ∈ B_{1}, akkor B definíciója szerint s ∈ I_{l}. u_{l} ∈ C_{1} pedig lehetetlen, mivel az 5.3.20. állítás szerint u_{l} és s függetlenek, hiszen ∧K′ ⪯ s. □

5.3.22. Állítás. C_{1} = ∅ vagy C_{1} = K, illetve C_{2} = ∅ vagy C_{2} = K′.

Bizonyítás. A szimmetria miatt elég a C_{1}-re vonatkozó állítást belátni. Tegyük fel indirekten, hogy az X = C_{1}, Y = B_{1} halmazok egyike sem üres. Alkalmazzuk erre partícióra az 5.3.15. állítást. Ekkor van olyan u_{i} ∈ C_{1}, u_{j} ∈ B_{1}, hogy u_{i} és u_{j} összefüggőek. Az előző állítás szerint ∧K′ ⪯ s ⪯ u_{j}, ellentmondásban az 5.3.20. állítással. □

C_{1} = ∅ lehetetlen, mivel ekkor minden u_{i} ∈ K = B_{1}-re s ⪯ u_{i} volna, ahonnan ∧K′ ⪯ s ⪯ ∧K következne, ellentmondásban azzal a feltevéssel, hogy ∧K és ∧K′ nem voltak rendezve. Tehát C_{1} = K, s ugyanígy C_{2} = K′. Ekkor azonban B = ∅ ellentmondást ad. □

5.4. Megvalósítás gráfokon

Megmutatjuk az algoritmus alkalmazását arra a speciális esetre, amikor egy adott D = (V, A) digráfot szeretnénk adott ∅ ≠ S, T ⊆ V halmazokra k-szorosan ST -összefüggővé növelni. Legyen P = A(S, T). A 3.2.3. rész jelöléseivel egy X ∈ A(V, V) ST -párra legyen p_{D}(X^{−}, X^{+}) := (k − δ(X^{−}, X^{+}) − h(X^{−}, X^{+}))^{+}. Legyen p a p_{D} vetítése A(S, T)-re; feladatunk most ezen p függvény fedése.

A ⪯-ra legkisebb P-beli párok (s, T −s) lesznek minden s ∈ S-re, a legnagyobbak pedig (S − t, t) minden t ∈ T -re.

A ∨ és ∧ műveletek metszet- és unióképzéssel végezhetőek. Egy I_{i} = [m_{i}, M_{i}] intervallumban levő összes elemet le tudjuk fedni azzal a s_{i}t_{i} éllel, amire s_{i} = m_{i}^{−}, t_{i} = M_{i}^{+}. Egy I intervallumrendszerre legyen E = {s_{i}t_{i} : i = 1, …, k}.

Készítsük el a 2.2.2. tétel bizonyításában szereplő gráfot, ahol a kapacitásfüggvény: g(x′x′′) = 1, g(x′′y′) = 1 minden xy ∈ A-ra. Ezen H hálózat legszűkebb illetve legbővebb minimális s′′t′ vágásai s ∈ S és t ∈ T esetén éppen a legkisebb illetve legnagyobb P-beli st̄ pároknak felelnek meg.

Úgy tudjuk eldönteni, hogy I fedés-e, hogy a D′ = (V, A+E) gráfban tetszőleges pontpárra ellenőrízzük, hogy köztük k-szorosan összefüggő-e a gráf. Azt, hogy az I_{j} intervallum tartalmaz-e szoros elemet, attól függ, hogy D′′ = (V, A + E − s_{j}t_{j}) s_{j} és t_{j} közt k-szorosan összefüggő-e. Ha nem, akkor Q_{j}, azaz I_{j} maximális szoros eleme a legnagyobb s_{j}t̄_{j} pár lesz, amit MFMC-vel tudunk meghatározni a H hálózaton.

A Pushdown(j) lépésben u_{j}^{(t+1)} meghatározásához először megkeressük azokat az iket, melyekre u_{i}^{(t)} alulról függ u_{j}^{(t)}-től. Legyen ezen i-k halmaza J. Tekintsük az alábbi intervallumrendszert (mely általában nem lesz fedés): I_{0} = I −I_{j} −{I_{i} : i ∈ J}+{[m_{i}, M_{j}] : i ∈ J}. Könnyen látható az alábbi:

5.4.1. Állítás. Minden z ∈ I_{j} I_{0}-ban legalább p(z) − 1-szer lesz fedve. Legyen y ∈ I_{j} a legnagyobb olyan szoros elem I-ben, ami semmilyen i ∈ J-re nem függ alulról u_{i}^{(t)}-től. Ekkor y a ⪯-ra legnagyobb olyan elem I_{j}-ben, mely I_{0}-ban nincs lefedve.

Ezt az y-t meg tudjuk találni folyamalgoritmussal. Könnyen látható továbbá, hogy u_{j}^{(t)} ∧ y lesz V maximális eleme, azaz u_{j}^{(t+1)}. Az algoritmus többi része egyszerűen végrehajtható.

5.4.1. Bonyolultság

Legyen L a leghosszabb lehetséges lánchossz, K pedig egy felső korlát k-ra, az intervallumok számára. Nevezzük triviálisnak azt a Pushdown(j, t) lépést, melynek során u_{j}^{(t+1)} = u_{j}^{(t)}, és nemtriviálisnak, ha u_{j}^{(t+1)} ≺ u_{j}^{(t)}. A nemtriviális Pushdown lépések száma legfeljebb LK. Mivel minden t-re legalább egy nemtriviális Pushdown van, így a triviálisok száma legfeljebb K-szor annyi, azaz O(LK^{2}). ST -összefüggőség növelése esetén L = n és K = n^{2} felső korlátok lesznek. Ez utóbbi azért, mert egy növelésben nem érdemes kétszer bevenni ugyanazt az élt.

A Pushdown(j, t) lépésben először meghatározzuk a J indexhalmazt, ami O(K) időben tehető meg. Ezzel együtt tudjuk ellenőrízni, hogy u_{j}^{(t+1)} = u_{j}^{(t)} teljesül-e, tehát egy triviális Pushdown ideje O(K). Ha ez nem teljesül, akkor u_{j}^{(t+1)} egy folyamszámítással kapható meg, O(MC) időben, azaz egy nemtriviális Pushdown összesen O(K +MC) időben történik. A Pushdown lépések összideje tehát O(LK^{3} + LK MC) A Reduce lépés során t^{∗} ≤ LK. Egy iteráció O(K) időben végrehajtható, tehát a Reduce ideje O(LK^{2}). A PushToMin egy lépésében csökken a különböző u_{i}-k száma, azaz a PushToMin ideje O(K). Így az algoritmus összbonyolultsága O(LK^{3} + LK MC) = O(n^{7} + n^{3}n^{3}) = O(n^{7}). Az ST -összefüggőség növeléséhez kiindulunk egy legfeljebb n^{2} elemű fedésből, arra legfeljebb n^{2}-szer végrehajtva ezt az algoritmust megkapjuk az optimális növelő élhalmazt, legfeljebb O(n^{9}) időben.

Ha a kiindulási gráfunk k − 1 összefüggő volt, akkor kicsit jobbat mondhatunk. A 4.6. részben leírt O(kn^{6}) idejű approximációs algoritmus az optimálisnál legfeljebb k − 1-gyel több élt ad meg. Ha ez a kiindulási fedés, akkor algoritmusunkat csak k-szor kell lefuttatni, ezért az összbonyolultság O(kn^{7}).

Irodalomjegyzék

[1] Frank A. és Jordán T., Minimal Edge-Coverings of Pairs of Sets, J. Combin. Theory, Ser B 65, (1995), pp. 73-110

[2] Frank A. és Jordán T., How to Make a Strongly Connected Digraph Two-Connected. IPCO (1995) pp. 414-425

[3] Frank A. és Jordán T., Directed vertex-connectivity augmentation Math. Program 84, (1999), pp. 537-553

[4] Frank A., Augmenting graphs to meet edge-connectivity requirements. SIAM J. Discrete Math. 5, No. 1 (Feb. 1992), pp. 22-53

[5] T. Watanabe és A. Nakamura, Edge-connectivity augmentation problems, Comput. System Sci. 35, No 1 (1987), pp. 96-144

[6] K. P. Eswaran és R. E. Tarjan, Augmentation problems, SIAM J. Comput. 5, No. 4 (Dec.

1976), pp. 653-665

[7] Győri E., A minimax theorem on intervals J. Combin. Theory, Ser B 37, (1984), pp. 1-9

[8] Frank A., Finding minimum generators of path systems, J. Combin. Theory Ser B, 75 n.2, (March 1999), pp.237-244

[9] Frank A., Finding minimum weighted generators of a path system, in: R.L. Graham, J. Kratochvil, J. Nesetril, F.S. Roberts (Eds.), Contemporary Trends in Discrete Mathematics, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, AMS, Providence, Rhode Island, Vol. 49, 1999, pp. 129-138.

[10] Benczúr A. A., J. Förster, Király Z. Dilworth’s Theorem and its application for path systems of a cycle - implementation and analysis, Proc. European Symp. Alg., Springer

Lecture Notes in Computer Science 1643 (1999) pp. 598-609

[11] Frank A., An Algorithm to Increase the Node-Connectivity of a Digraph, in: Proceedings of the 3rd Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications, Tokyo, Japan (2003), 378-387.

[12] Benczúr A. A., Pushdown-reduce: an algorithm for connectivity augmentation and poset covering problems, Discrete Applied Mathematics 129, (2003), pp. 233-262 [13] S. Enni, A 1-(S, T)-edge-connectivity augmentation algorithm, Math. Program 84, (1999),

pp. 529-535

[14] Jordán T., Increasing the vertex-connectivity in directed graphs, in: Proceedings of the First Annual European Symposium on Algorithms, Bad Honnef, 1993, Springer Lecture Notes In Computer Science, Vol 726, pp. 236-247, Springer-Verlag, New York/Berlin, 1993

[15] Jordán T., On the optimal vertex connectivity augmentation, J. Combin. Theory Ser. B. 63, (1995) pp. 8-20.

[16] Jordán T. és B. Jackson, Independence free graphs and vertex connectivity augmentation, EGRES Tech. Report TR-2001-04

[17] W. Mader, Minimal n-fach zusammenhängende Digraphen, J. Combin. Theory Ser B, 38, (1985), pp.102-117

[18] M.R. Henzinger, S. Rao, H.N. Gabow, Computing vertex connectivity: New bounds from old techniques Journal of Algorithms 34, 2, (2000) pp. 222-250

[19] Frank A., Válogatott fejezetek a kombinatorikus optimalizálásból (egyetemi jegyzet)

     (2003) http://www.cs.elte.hu/~frank/jegyzet/valfej2003.ps.gz

[20] Frank A., Kombinatorikus algoritmusok II. (egyetemi jegyzet) (2003)

     http://www.cs.elte.hu/~frank/jegyzet/kombal2003.ps.gz