Mathematics | Higher education » Hajba Tamás - Approximációs algoritmusok k-összefüggő részgráfok keresésére

Approximcis algoritmusok k-sszefgg rszgrfok keressre Szakdolgozat rta: Hajba Tams Tmavezet: Frank Andrs egyetemi tanr ELTE Termszettudomnyi Kar Opercikutatsi Tanszk 1998. Tartalomjegyzk 1. Bevezets 2. IRNYTATLAN GRFOK 2.1 Pontsszefgg problmk 2.11 S lyozatlan pontsszefggsg 2.12 S lyozott pontsszefggsg 2.2 lsszefggsgi problmk 2.21 S lyozatlan lsszefggsg 2.22 S lyozott lsszefggsg . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 6 6 6 11 14 15 22 3. IRNYTOTT GRFOK 23 4. LTALNOSTOTT STEINER FELADAT 31 3.1 Ers sszefggsg 23 3.2 Tbbszrs sszefggsg 27 4.1 Priml-dul algoritmus 32 4.2 Egy 2 faktor approximci 40 2 1. Bevezets Az utbbi vtizedekben a gyakorlati

alkalmazsok miatt az NP-teljes problmk j kzelt megoldst szolgltat heurisztikk illetve algoritmusok egyre fontosabb szerepet kapnak. Egy lehetsges megkzeltsi md approximcis algoritmusok hasznlata Egy faktor approximcin olyan polinomilis algoritmust rtnk, mely bizonytottan nem ad rosszabb megoldst mint az optimum -szorosa. Az approximcis algoritmusok mindig magukban foglaljk az optimum als becslst, s gy kzvetve a problma mlyebb megrtsben is segtenek. A szakdolgozat clja a grfok NP-teljes sszefggsgi problmira vonatkoz approximcis algoritmusok ttekintse. A szakdolgozat a Hochbaum 1] knyv 4. s 6 fejezetnek fontosabb algoritmusait s az jabb eredmnyeket tartalmazza A 2. s 3 fejezetben a kvetkez problmra ismertetnk approximcis algoritmusokat: egy k-sszefgg ls lyozott grfnak keressnk minimlis s ly k-sszefgg rszgrfjt. A feladatnak 4 verzija lehetsges, attl fggen, hogy a grf irnytott vagy irnytatlan

illetve pontsszefgg vagy lsszefgg. A feladat irnytatlan grfoknl k 2 esetn mr azonosan egy s lyozsnl, mg irnytott esetben k 1 esetben az azonosan egy s lyozsnl is NP-teljes. Azonban kiderl, hogy 2 faktor approximcit szinte mindegyik esetben knny adni. Tbbfajta tpus algoritmus ltezik Az egyik gyakran hasznlt mdszer mlysgi fk hasznlata. Pldul 2-lsszefgg rszgrf keressnl elnyt jelent, hogy egy mlysgi fban nincsenek keresztlek, ezrt az elvg lek csak a fa lei lehetnek. Nhny algoritmus a prostsok elmletn alapul: Seb, Szigeti s Cheriyan algoritmusa azt hasznlja, hogy egy 2-lsszefgg grfnak ltezik megfelel flfelbontsa. Mindegyik algoritmusnl fontos szerepet jtszik az optimum als becslse. J becslsekre tbbfajta ttelt is fogunk ltni. A 4. fejezetben egy ltalnosabb feladatot trgyalunk: irnytatlan grfnak kell keresni minimlis s ly rszgrfjt, mely minden vgsbl legalbb elre megadott szm let tartalmaz. A

feladat specilis esete az ltalnostott Steiner problma, amikor is a pontok kztti loklis lsszefggsgre van egy elrs. A fejezetben szerepl algoritmusok a feladat lineris programknt val megfogalmazst hasznljk. Williamson algoritmusa a priml s dul vltozkat javtja addig, mg a feladatra kap egy megengedett megoldst. Az algoritmus sorn arra vigyzunk, hogy a priml complementary slackness mindvgig fennljon, mg a dul complementary slackness tlagosan fog teljeslni. Kamal Jain algoritmusa iteratven megoldja az LP relaxcit majd kerekti a megoldst. Az algoritmus lnyege, hogy minden lpsben legalbb eggyel cskken az lek szma. 3 De n cik Legyen G = (V E ) egy irnytatlan grf. G-t k-pontsszefggnek nevezzk , ha jV j > k ; 1 s G-ben brhogy trlnk el legfeljebb k ; 1 pontot, a maradk grf sszefgg marad. G-t k-lsszefggnek nevezzk, ha G-ben brhogy trlnk el legfeljebb k ; 1 let, a maradk grf sszefgg marad. Egy S  V

ponthalmazra jellje (S ) azon lek halmazt, melyeknek pontosan az egyik vgpontja van S -ben. Ha adott G-ben egy T feszt fa s egy r 2 V pont, akkor a (T r) prt gykeres fnak nevezzk, s azt mondjuk, hogy r a T gykrpontja. Legyen (T r) egy gykeres fa Azt mondjuk, hogy az u 2 V pont a v 2 V pont se, ha u rajta van a v-bl r-be vezet T -beli ton. A v pontot ekkor az u pont leszrmazottjnak hvjuk Ha radsul (u v) 2 T , akkor az u pontot a v szljnek, v-t pedig u nak nevezzk. Az (x y) 2 E ; T let visszalnek nevezzk, ha valamelyik vgpontja se a msik vgpontnak. Ha egyik vgpontja sem se a msik vgpontnak, akkor az (x y) let keresztlnek nevezzk. Egy irnytott grfot ersen sszefggnek hvunk, ha brmely pontbl brmely pontba ltezik irnytott t. Egy irnytott grfot k-pontsszefggnek neveznk, ha legalbb k pontja van s brhogy trlnk el legfeljebb k ; 1 pontot, a maradk grf ersen sszefgg marad. Egy irnytott grfot k-lsszefggnek

neveznk, ha brhogy trlnk el legfeljebb k ; 1 let, a maradk grf ersen sszefgg marad. Egy irnytott grfot grfot fenynek hvunk, ha valamely s pont befoka 0, s minden ms pont befoka 1. Az s pontot a feny gykernek nevezzk Ha adott egy grf (irnytott vagy irnytatlan) s egy c : E ! R ls lyozs, akkor tetszleges E lhalmaz slyn a benne szerepl lek s lynak sszegt rtjk, s c(E )-vel jelljk. Egy k-sszefgg G grf egy e lt kritikusnak nevezzk, ha G ; e nem k-sszefgg. Legyen G egy irnytott (irnytatlan) grf, s s egy adott pontja. Jellje S a s pontbl elrhet pontok halmazt. Ekkor ltezik egy s gyker F feny (gykeres fa), melynek ponthalmaza S . F -t a kvetkez cmkzsi technika segtsgvel tallhatjuk meg: minden ponthoz tartozik 2 cmke, egy EL RT s egy TVIZSGLT. Az algoritmus kezdetn az s pont elrt, a tbbi pont nem elrt, s minden pont NEM TVIZSGLT. Az algoritmus egy lpsben vesz egy mr elrt, de mg nem tvizsglt u pontot.

Ha az u pontbl megy ki olyan (u v) l, melyre v mg nem elrt, akkor v-t elrtt nyilvntjuk, s az (u v) let betesszk a v pont EL RT cmkjbe. Ha az u pontbl nem megy ki olyan (u v) l, melyre v mg nem elrt, akkor az u pontot TVIZSGLTNAK nyilvntjuk, s iterljuk az eljrst. Knnyen belthat, hogy az algoritmus vgn az elrt pontok EL RT cmkjben lv lek egy s gyker fenyt (gykeres ft) alkotnak, melynek ponthalmaza S . 0 0 4 Ha az algoritmus sorn mindig azt a mg nem tvizsglt pontot vlasztjuk ki, melyet a legkorbban rtnk el, akkor az algoritmust szlessgi keressnek nevezzk. Ha mindig azt a mg nem tvizsglt pontot vlasztjuk ki, melyet a legksbb rtnk el, akkor az algoritmust mlysgi keressnek nevezzk. A loklis szlessgi keress a szlessgi keress ltalnostsa: az algoritmus mindig vesz egy elrt de mg nem tvizsglt u pontot, s beteszi a fenybe az sszes olyan (u v) lt, melyekre v mg nem elrt. Az Ax  b x 0 (A 2 R m n  x

2 R n  b 2 R m ) egy x0 megengedett megoldst bzismegoldsnak neveznk, ha azon sorok rangja, melyeket x0 egyenlsggel teljest, megegyezik A rangjval. Legyen V egy vges alaphalmaz. Azt mondjuk, hogy az S  V s az S  V halmazok metszek, ha az S ; S  S ; S S S halmazok egyike sem az reshalmaz. Egy S  2V halmazrendszert laminrisnak neveznk, ha semmelyik kt halmaza sem metszi egymst. Egy approximci n olyan polinomilis algoritmust rtnk, mely az optimumnl legfeljebb -szor ad rosszabb megoldst.  0 0 5 0 0 2. IRNYTATLAN GRFOK 2.1 Pontsszefgg problmk Ebben a fejezetben a kvetkez problmval foglalkozunk: adott egy G = = (V E ) irnytatlan k-pontsszefgg grf s c : E ! R + s lyfggvny. Keressnk minimlis s ly k-pontsszefgg rszgrfot a V ponthalmazon. A tovbbiakban jelljn Gopt = (V Eopt ) egy minimlis s ly k-pontsszefgg rszgrfot. Az els rszben azt az esetet trgyaljuk, mikor minden s ly egyenl 1-gyel, mg a msodik rszben az

ltalnos esetet nzzk. 2.11 S lyozatlan pont sszef gg sg Adott egy G = (V E ) irnytatlan k-pontsszefgg grf. Keressnk G-nek minimlis lszm k-pontsszefgg rszgrfjt. Cheriyan s Thurimella 2]-ben adott egy egyszer 2 approximcit: loklis szlessgi keresssel vegynk egy F1 maximlis erdt, hagyjuk el az leit, majd a maradk grfbl loklis szlessgi keresssel vegynk ki egy F2 maximlis erdt, stb. Ekkor Ek = F1  F2 : : :  Fk k-pontsszefgg grf lesz, melynek lszma legfeljebb (k ; 1)k=2 + (n ; k)k. Mivel minden k-pontsszefgg grfban minden pont foka legalbb k, ezrt jEoptj kn=2, ezrt az algoritmus egy 2 approximci. A k = 2 esetre Khuller s Vishkin 3]-ban adott 5=3-os approximcit. Az algoritmus vesz egy mlysgi ft, melyet visszalek hozzadsval 2pontsszefggv tesz. Garg, Santosh s Singla 4]-ben az algoritmus mdostsval az approximcis faktort 3=2-re javtotta k > 2 esetn sokig nem ismertek 2 faktornl jobb approximcit.

Cheriyan s Thurimella 5]-ben prostsok segtsgvel tetszleges k-ra adott egy 1 + 1=k faktor approximcit. k-pont sszef gg sg: Cheriyan s Thurimella algoritmusa: Az algoritmus 2 fzisbl ll. Az els fzisban meghatroz egy minimlis elemszm M lhalmazt, hogy minden v 2 V pontra dM (v) k ; 1. Ez lnyegben egy b-pros ts feladat A b-prosts feladat a maximlis prostsnak az ltalnostsa: minden v pontra adott egy bv egsz szm, talljunk maximlis szm N  E lhalmazt, hogy minden v pontra dN (v)  bv . Gabow s Tarjan 24]-ben megmutatta, hogy a b-prosts feladat O(jE j1:5(logjV j)1:5) lpsben megoldhat. Esetnkben M megtallsa ekvivalens egy N  E megtallsval, melyre dN (v) d(v) ; k + 1 minden v pontra. Az elz megjegyzs szerint M 6 O(jE j1:5(logjV j)1:5) idben megtallhat. A msodik fzisban egy tartalmazsra nzve minimlis F lhalmazt keresnk, amelyre M  F k-pontsszefgg lesz. F megkeresse: kezdetben legyen F = = s az aktulis grf pedig G.

Tetszleges sorrendben megvizsgljuk E ; M leit. Ha egy e l kritikus (azaz az aktulis grfbl elhagyva mr nem lesz k-pontsszefgg a maradk grf), akkor az e lt hozzvesszk F -hez, ha pedig e nem kritikus, akkor trljk az aktulis grfbl. Egy (u v) l pontosan akkor kritikus, ha az u s v pont kztt nem ltezik k + 1 diszjunkt t, gy egy l kritikussgt O(kjE j) idben eldnthetjk. A 2 fzis futsideje O(kjE j2). Az eljrs vgn M  F k-pontsszefgg lesz, s F minden le kritikus lesz. Most M -re s F -re vonatkoz fels becslseket fogunk adni. Bizonyts nlkl hasznlni fogjuk Mader 6]-beli ttelt: 2.1 Ttel Egy k-pontsszefgg grfban egy kritikus lekbl ll krnek van olyan pontja, melynek a foka pontosan k. 2.2 Lemma jF j  n ; 1 Bizonyts. Tekintsk a G = (G M  F ) grfot Ez k-pontsszefgg s 0 minden F -beli l kritikus. Ha F -beli lekbl ltezne egy C kr, akkor M dencija miatt G -ben a C kr minden cs csnak legalbb k + 1 lenne a foka, ami

ellentmond Mader ttelnek. Teht F aciklikus, gy  n ; 1 szm le van. 2.3 Ttel Legyen G = (V E ) egy k-pontsszefgg grf, M  E pedig olyan lhalmaz, hogy dM (v)  k ; 1 8v 2 V . Ekkor jM j  jEopt j ; bn=2c Bizonyts. Ha Gopt-ban ltezik teljes prosts, akkor az llts trivilis Ha nem ltezik Gopt-ban teljes prosts, akkor a Gallai-Edmonds ttel szerint ltezik egy X  V ponthalmaz, melyet Gopt-bl elhagyva a keletkez pratlan komponensek faktorkritikusak, s szmuk jX j, a pros komponensekben pedig ltezik teljes prosts. Tekintsk a kvetkez G = (S  T E ) pros grfot: legyen S = X , T pontjai legyenek a pratlan komponensek, E pedig lljon az X halmazbl a pratlan komponensekbe men G-beli lekbl. Mivel a G grf k-pontsszefgg, ezrt G -ben minden T -beli pont foka legalbb k. Sznezzk meg G -t k sznnel egyenletesen, azaz bontsuk fel E -t E1  : : : Ek nemres diszjunkt halmazokra gy, hogy minden v 2 S  T pontra b dGk(v) c  dEi (v)  b dGk(v) c + 1:

1ik 7 0 0 0 0 0 0 0 0 0 Ismert, hogy minden pros grf lhalmaza brmely k-ra egyenletesen kisznezhet. Hagyjuk el G -bl mondjuk az E1 sznosztlyt. Az egyenletes sznezs miatt a maradk grfban minden T -beli pont foka legalbb k ; 1. Az eredeti G grfban vegynk egy M  E1 lhalmazt, mely minden pratlan komponensbl egy kilp let tartalmaz. Ha ehhez az M -hz hozzvesszk a pratlan komponensek maradk pontjainak egy teljes prostst s a pros komponensek egy teljes prostst, akkor egy legalbb bjV j=2c nagysg lhalmazt kapunk, melyet Gopt -bl elhagyva minden pont foka legalbb k ; 1. Ezrt a minimlis lszm M lhalmazra, melyre dM (v) k ; 1 minden v 2 V pontra, jM j  jEoptj ; bn=2c. 0 0 0 2.4 Ttel Legyen G = (V E ) egy k-szor pontsszefgg grf A fenti algoritmus G-nek egy G = (V E ) k-pontsszefgg rszgrfjt tallja meg, melyre jE j  (1 + 1=k)jEoptj. Az algoritmus futsideje O(k3jV j2 + jE j1:5(logjV j)2). 0 0 0 Bizonyts. jE j = jM j +

jF j  jEoptj ; (n ; 1)=2 + n ; 1  1 + 1=k: jEoptj jEopt j jEoptj A msodi fzis futsidejt O(k3jV j2)-re javthatjuk, ha elszr vesszk G egy legfeljebb nk l E k-pontsszefgg rszgrfjt, s a 2. fzist M  E -re 0 0 0 futtatjuk. 2-pont sszef gg sg Ebben a rszben Garg, Santosh s Singla lineris idej algoritmust ismertetjk minimlis lszm 2-pontsszefgg rszgrf keressre. Az algoritmus sorn a grf egy blokkjn pontoknak egy rszhalmazt rtjk, teht nem a grfelmleti jelentse szerint hasznljuk (azaz egy blokk nem a 2-pontsszefgg komponenseket jelenti). Az algoritmus 2 fzisbl ll Az els fzisban vesz egy S lhalmazt, amely egy 2-pontsszefgg rszgrfjt hatrozza meg G-nek. Tovbb az els fzisban a pontokat blokkokba osztja, majd ezen blokkok segtsgvel a msodik fzisban mdostja S -t. 1. fzis: Vegynk egy s gyker T mlysgi ft Egy v pontra jellje dfs(v), hogy a mlysgi keress hnyadiknak rte el v-t. Mikor a keress sorn egy u pontot

tvizsgltunk, s visszalpnk a v szljre, akkor megnzzk, hogy az aktulis grfban v szepartor-e. Ha igen, akkor S -hez hozzvesznk egy (x y) visszalt, melyre x az u leszrmazottja, dfs(y) pedig minimlis. A tovbbiakban ezeket az leket legmlyebb 8 visszalnek nevezzk. Tovbb u azon leszrmazottjaibl, melyek mg nincsenek benne blokkban, csinlunk egy j blokkot A mlysgi keress vgn azon pontokbl, melyek nincsenek benne egyik blokkban sem, csinlunk egy blokkot. Az 1. fzis vgn minden v ponthoz ltezik S -ben legalbb egy legmlyebb visszal, mely v valamely st v valamely leszrmazottjval kti ssze, ezrt S 2-pontsszefgg lesz. Lthat, hogy a T fa lei minden blokknak egy feszt fjt adjk. H zzuk ssze a T mlysgi fban a blokkokat egy pontt, jellje az gy kapott ft T , s legyen T gykere a T gykert tartalmaz blokk. A T gykeres fa segtsgvel rtelmezni tudjuk a blokkok kzti szl-gyerek viszonyt. 2.5 Denci Azt mondjuk, hogy a v pont a B

blokk szlpontja, ha v eleme a B blokk szlblokkjnak, s v s B kztt ltezik T -beli fal. Az els fzisban alkalmazott eljrsbl azonnal addik az albbi lemma: 2.6 Lemma G minden le vagy egy blokkon bell, vagy egy blokk s a szlblokkja kztt, vagy egy blokk s a szlblokkjnak a szlpontja kztt megy. 0 0 0 2.7 Lemma Ha egy B blokk v pontjbl B semmelyik gyerekblokkjba nem megy l G-ben, akkor v-bl B semmelyik leszrmazott blokkjba sem megy G-beli l. Bizonyts. A felttel miatt v nem szlpontja a B blokk egyetlen gyerek- blokkjnak sem, amibl a 2.6 Lemma alapjn kvetkezik az llts Az els fzis utn minden nem gykr blokkbl megy ki egy legmlyebb visszal. A msodik fzis sorn ezen visszaleket mdostjuk gy, hogy vagy minden blokkbl elhagyhatunk egy fa let, vagy ha ez nem lehetsges, akkor tallunk egy nagy fggetlen ponthalmazt. Az lelhagyst az albbi egyszer lemma miatt hajthatjuk vgre: 2.8 Lemma Legyen G egy 2-szer pontsszefgg grf C

egy kr G -ben, e = (u v) a C egy h rja. Ekkor G ; e 2-szer pontsszefgg 2. fzis: A msodik fzis sorn a gykr blokktl a levl blokkok fel haladva minden blokk a gyerek blokkjaibl indul viszalek mdostsrl fog dnteni. Tegyk fel, hogy a B blokknl vagyunk. Legyen (v u) a B -bl indul viszszal, ahol v 2 B Nzzk a fban a v-bl a B blokk p szlpontjba men 0 0 0 9 u u p p B B s v B’ s’ B’’ s r r’ t’ v B’ t t (a) (b) 1. bra: utat. Legyen s ennek az tnak a legels olyan pontja (v-t is belertve), amely az ttl eltekintve nem tartalmaz fa lt. Ha ilyen pont nem ltezik, akkor s legyen p-vel egyenl. (1 bra) 1. eset: Ltezik egy (t s) visszal, t 2 B , B a B gyerek-blokkja. Ahelyett, hogy a B -bl kiindul legmlyebb visszalt vennnk, vegyk a megoldshoz a (t s) visszalt, B tbbi gyerekblokkjban nem mdostjuk az els fzis sorn vett visszaleket. Vilgos, hogy az j grf tovbbra is 2-pontsszefgg marad 1.1 eset: s = p(v)

Ekkor (s v) h rja az u ; v ; ;t ; s ; ;p ; ;u krnek, gy az (s v) fal elhagyhat. 1.2 eset: s 6= p(v) Legyen (r  r) (r s) a T fa v-bl s-be men tjnak utols 2 le. 1.21 eset:A T fban a t ; s t tmegy az (r  r) len Az s-re tett feltevs miatt r-bl az (r  r), (r s) leken kvl is megy fa l. Menjen ez az l a B blokk egy B gyerek blokkjba. Ekkor ltezik egy (t  s ) visszal, melyre t 2 B , s pedig az s s p kzti T fa-beli ton van. Ekkor az (r s) l h rja az r ; ;t ; s ; ;s ; t ; ;r krnek, gy elhagyhat. 1.22 eset: A T fban a t ; s t nem megy t az (r  r) len Ekkor (r s) h rja a s ; ;p ; ;u ; v ; ;r ; ;t ; s krnek, gy elhagyhat. Teht az els esetben mindig kidobhat egy fal. 0 0 0 0 0 0 00 0 00 0 0 0 0 0 0 2.eset: semmelyik gyerek-blokkbl sem megy s-be l A s pontot hozz- vesszk az M halmazhoz. 2.9 Lemma Az M -beli pontok fggetlenek Bizonyts. AZ M -beli pontok klnbz blokkokban vannak, s egy M beli pontba semmelyik gyerek-blokkbl

nem vezet l, gy a 27 Lemma alapjn 10 kt M -beli pont kztt nem mehet l. 2.10 Ttel A fenti algoritmus O(E ) lpsben megtallja G egy 2-pontsszefgg rszgrfjt, melynek lszma legfeljebb 3=2-szerese az optimumnak Bizonyts. Mivel M egy fggetlen ponthalmaz, gy egy optimlis 2-pontsszefgg rszgrfnak legalbb max(n 2jM j) le van. Msrszt a 2 fzisban pontosan akkor nem hagyunk el egy blokkbl egy falet, ha ennl a blokknl az M halmazt j elemmel bvtjk, ezrt az algoritmus ltal vett n ; 1 + jM j approximcis lek szma n ; 1 + jM j, gy az algoritmus egy max( n 2jM j) faktort r el, ami legfeljebb 3=2. A lpsszmra vonatkoz llts knnyen lthat. 2.12 S lyozott pont sszef gg sg Az ltalnos esetben az leken adott egy w nemnegatv s lyozs, s keresni kell egy minimlis s ly k-pontsszefgg rszgrfot. Az ltalnos esetben nem ismert konstans faktor approximci. A jelenleg ismert legjobb algoritmust Ravi s Williamson adta 16]-ban, amely egy 2H (k)

approximci, ahol H (k) = 1+1=2+ :::1=k. Az algoritmus egy primldul algoritmus, melyet egy ksbbi fejezetben ismertetnk Ha a s lyfggvny kielgti a hromszg-egyenltlensget, akkor Khuller s Raghavachari 7]-ben adott egy 2 + 2 k n 1 approximcit. k = 2 esetn Khuller s Raghavachari 7]-ben adott egy 2 + 1=n-es approximcit. Ezt az algoritmust kicsit mdostva Penn s Shasha-Krupnik 8]-ban adott egy 2 -szeres approximcit. k = 3 esetn Nutov s Penn 19]-ben adott egy 3 approximcit. Mindhrom algoritmus lnyege a kvetkez algoritmus: 2.11 Feladat Adott egy G = (V E ) irnytatlan k-pontsszefgg grf lein nemnegatv s lyokkal, s R  V k darab pont. Keressnk minimlis s ly E  E lhalmazt gy, hogy G = (V E )-ben minden v 2 V pontbl ltezik R-be k darab pontdiszjunkt t. AZ IRNY!TATLAN FT(G k R) algoritmus a kvetkez: ksztsk el G irnytott vltozatt: minden l helyett vegynk 2 ellenttesen megirnytott let az eredetivel megegyez s lyokkal. Vegynk fel

egy j r pontot, s h zzunk belle minden R-beli ponthoz k darab 0 s ly irnytott lt. Frank s Tardos 9]-ben megmutatta, hogy a kvetkez problma polinomilis idben megoldhat: Adott egy D irnytott grf, lein nemnegatv ; 0 0 11 0 s lyok, s egy r gykrpont. Talljunk minimlis s ly irnytott H rszgrfot gy, hogy D minden v pontjhoz ltezzk r-bl k darab pontdiszjunkt t Alkalmazzuk Frank s Tardos algoritmust az j grfra. !gy kapunk egy minimlis s ly H rszgrfot, melyben minden ponthoz ltezik r-bl k darab pontdiszjunkt irnytott t. Legyen S  E azon lei G-nek, melyeknek megfelel 2 irnytott l kzl legalbb az egyik benne van H -ban. H konstrukcija miatt minden G-beli pont s R kztt ltezik S -ben k darab pontdiszjunkt t. 2.12 Lemma w(S )  2w(Eopt) ahol Eopt egy minimlis s ly k-pontsszefgg rszgrf. Bizonyts. Ksztsk el a fenti mdon Eopt irnytott vltozatt !gy egy olyan H irnytott grfot kapunk, melyben r-bl minden V -beli pontba

ltezik k darab pontdiszjunkt t, s w(H ) = 2w(Eopt). Mivel H minimlis s ly rszgrf , melyben r-bl minden V -beli pontba ltezik k darab pontdiszjunkt t, ezrt w(S )  w(H )  w(H ) = 2w(Eopt). 2.13 Ttel (Khuller s Raghavachari): Ha a s lyfggvny kielgti a hromszg-egyenltlensget, akkor ltezik egy 2 + 2(k ; 1)=n approximcis algoritmus. Az algoritmus a kvetkez: A hromszg-egyenltlensg miatt feltehet, hogy a G grf teljes, s az lek s lya egyenl a vgpontjaikat sszekt legrvidebb t hosszval. Az algoritmus elszr megkeresi a minimlis s ly k pont csillagot Jellje ezt a grfot S (i), ahol i a csillag kzppontja, s legyen R a csillag ponthalmaza. Ezutn meghvja az IRNY!TATLAN FT(G k R)-t, gy kapunk egy S rszgrfot. Az algoritmus vgl az S  KR grfot adja ki, ahol KR az R-beli pontok ltal meghatrozott teljes grf. 2.14 Lemma S  KR k-pontsszefgg Bizonyts. Tegyk fel indirekt, hogy ltezik jC j  k ; 1 pont, melyeket elhagyva S  KR sztesik C1

::Cl , l 2 komponensekre. Mivel az R-beli pontok szomszdosak, ezrt valamely i-re R  C  Ci. Mivel jC j  k ; 1 ezrt i 6= j esetn egy Cj -beli pontbl nem ltezhet k darab pontdiszjunkt t R-be, ami ellentmond S dencijnak. 2.15 Lemma w(KR )  2(k n; 1) w(Eopt) 0 0 0 12 Bizonyts. Jellje N (j ) a Gopt-beli minimlis s ly j kzppont k-csillagot (ilyen ltezik, mert Gopt-ban minden pont foka legalbb k) Mivel S (i) egy minimlis s ly csillag G-ben, ezrt 8j -re w(S (i))  w(N (j )). Msrszt Xn w(N (j))  2w(Eopt) j =1 hiszen minden lt legfeljebb 2-szer szmolunk. !gy w(S (i))  n2 w(Eopt): A hromszg-egyenltlensg miatt knnyen lthat, hogy w(KR)  (k ; 1)w(S (i)): A kt egyenltlensgbl kvetkezik,hogy w(KR)  2(k n; 1) w(Eopt): 2.16 Ttel w(S  KR)  (2 + 2(k ; 1)=n)w(Eopt) Bizonyts. Az 212 Lemma alapjn w(S )  2w(Eopt), az elz lemma szerint pedig w(KR)  2(k n; 1) w(Eopt). A fenti algoritmus k = 2 esetn akkor is mkdik, ha a s lyfggvnyre nem

teljesl a hromszg-egyenltlensg. Az algoritmus elszr vesz egy minimlis s ly e = (u v) lt R = fx yg-ra alkalmazva az IRNY!TATLAN FT(G 2 R) algoritmust kapunk egy S lhalmazt. Az elz algoritmusnl hasznlt bizonytsok miatt S  e 2-szer pontsszefgg lesz, s s lya legfeljebb (2 + 1=n)-szerese az optimumnak. Penn s Shasha-Krupnik8]-ban megmutatta, hogy ha az IRNY!TAT- LAN FT(G 2 R) algoritmust nem csak a minimlis s ly lre, hanem az sszes lre kln-kln lefuttatjuk, s az Se  e grfok kzl vesszk a minimlis s ly t, akkor egy 2 approximcit kapunk. Bizonyts. Legyen f = (u v) a Gopt egy le Legyen D az Eopt ; f irnytott vltozata. Ekkor w(D) = 2w(Eopt) ; 2w(f ), tovbb D-ben r-bl minden pontba vezet kt pontdiszjunkt t. Ezrt w(Sf )  2w(Eopt) ; 2w(f ) 13 amibl min fw(Se) + w(e)g  w(Sf ) + w(f )  2w(Eopt) ; w(f )  2w(Eopt): e 3-pont sszef gg sg Nutov s Penn 19] algoritmusa: 1. Vlasszunk ki egy tetszleges c1 pontot Legyen (c1 c2) s

(c1 c3) a c1-gyel szomszdos kt legolcsbb l. Legyen C3 := fc1 c2 c3g, s alkalmazzuk az IRNY!TATLAN FT(G,3,C3)algoritmust Jellje R(G C3) a kapott irnytatlan grfot. Ez egy olyan grf, melyben minden pontbl ltezik R-be 3 pontdiszjunkt t, s a s lya legfeljebb 2-szerese a minimlis 3-pontsszefgg rszgrf s lynak. 2. Az R(G C3)  (c1 c2)  (c1 c3 ) lek s lyt cskkentsk 0-ra, s talljunk G ; c1 -ben c2 s c3 kztt 2 pontdiszjunkt utat minimlis sszs llyal. Legyen F a kt t lhalmaza. 3. Legyen E = (R(G C3)  F  (c1 c2 )  (c1  c3)): 0 2.17 Ttel (V E ) 3-pontsszfgg, s w(E )  3w(Eopt), ahol Eopt egy 0 0 minimlis s ly 3-pontsszefgg rszgrf. Az algoritmus O(n2m) lpst tesz. Bizonyts. Tegyl fel, hogy E nem 3-pontsszefgg, azaz ltezik egy jC j < 3 szeparl ponthalmaz. Mivel (c1 c2) 2 E s (c1 c3) 2 E tovbb 0 0 0 c2 s c3 kztt ltezik 3 pontdiszjunkt t, ezrt C3 benne van C valamely komponensnek s C -nek az unijban. Ekkor

azonban E -ben C egy msik komponensbl nem mehetne C3 -ba hrom pontdiszjunkt t, ami bizonytja az ellentmondst, azaz a kapott grf 3-pontsszefgg. Felhasznlva, hogy Eopt -ban c1 foka legalbb 3, tovbb c1 legkzelebbi szomszdai c2 s c3 kapjuk, hogy w(F  (c1  c2)  (c1  c3))  w(Eopt). Tudjuk, hogy w(R(G C3))  2w(Eopt), gy w(E )  3w(Eopt). Az algoritmus els fzist O(n2m) lpsben meg lehet csinlni, F -t pedig O(m + nlogn) lpsben meg lehet tallni. 0 0 2.2 lsszefggsgi problmk Ebben a fejezetben a kvetkez problmt trgyaljuk: adott egy G = (V E ) irnytatlan k-lsszefgg grf nemnegatv ls lyokkal. Talljunk G-ben minimlis s ly k-lsszefgg rszgrfot A fejezet sorn Gopt = (V Eopt ) egy optimlis megoldst fog jellni. 14 2.21 S lyozatlan l sszef gg sg Adott egy n pont , m l irnytatlan k-lsszefgg G grf, keressnk minimlis elemszm k-lsszefgg rszgrfjt. Tetszleges k-ra Nishizeki s Poljak 23]-ban adott egy 2

approximcit. Az algoritmus vesz a G grfban egy maximlis F1 erdt, elhagyja az leit s a maradk grfban vesz egy F2 maximlis erdt, stb. Az Ek = = F1  F2 : : : Fk grf G egy k-lsszefgg rszgrfja lesz, melynek lszma legfeljebb kn. Mivel jEoptj kn=2, ezrt ez egy 2 approximcit ad Khuller s Raghavachari 7]-ben adott egy 1:85 faktor approximcit. Az algoritmus fzisokbl ll, s minden fzisban az sszefggsget 2-vel nveli 5]-ben Cheriyan s Thurimella adott egy 1 + 2=(k + 1)] faktor approximcit. Az algoritmus lnyegben megegyezik a pontsszefgg esetben hasznlt algoritmussal: elszr egy minimlis M lhalmazt tall meg, melyre minden v pontra dM (v) k. Ezutn egy tartalmazsra nzve minimlis F lhalmazt keres, melyre M  F k-lsszefgg. Az algoritmus futsideje O(k3jV j2 + + jE j1:5(log jV j)2). k = 2-re Khuller s Vishkin 3]-ban adott 1:5-szeres approximcit. Az algoritmusuk vesz egy mlysgi ft, majd ezt visszalek hozzadsval 2 lsszefggv teszi.

A jelenleg ismert legjobb approximcit Seb, Szigeti s Cheriyan adta 10]-ben: az algoritmus flfelbontst hasznl s 17=12-es approximcit ad. 2-l sszef gg sg Khuller s Vishkin2] algoritmusa: Az algoritmus sorn a grf egy blokkjn pontoknak egy rszhalmazt rtjk, teht nem a grfelmleti jelentse szerint hasznljuk (azaz egy blokk nem a 2-pontsszefgg komponenseket jelenti). Mlysgi keresssel vegynk egy T ft. A fa minden le benne lesz a megoldsban A mlysgi keress sorn mikor egy u pontot tvizsgltunk, s visszalpnk a v sre, megnzzk, hogy az aktulis grfban az (u v) l vgs-e. Ha igen, akkor a megoldshoz hozzvesznk egy (x y) visszalt, melyre x az u leszrmazottja, s ezen bell dfs(y) minimlis. Ezen kvl u azon leszrmazottaibl, melyek mg nincsenek benne blokkban, csinlunk egy blokkot A mlysgi keress vgn azon pontokbl, melyeket mg nem tettnk bele egyetlen blokkba sem, szintn csinlunk egy blokkot. Az algoritmus vgn lesz egy

2-lsszefgg rszgrfunk, s a pontoknak egy partcija 2.18 Denci Egy G grf ponthalmaznak egy V1 : : : Vk partcijt fafelbontsnak nevezzk, ha a Vi-ken mint ponthalmazon ltezik egy F fa gy, 15 hogy minden v 2 Vi pontnak a G-beli szomszdai vagy Vi-ben, vagy valamely Vi-vel F -ben szomszdos Vj halmazban vannak. k a fafelbonts nagysga 2.19 Ttel Ha a G = (V E ) grfnak van egy k nagysg fafelbontsa, akkor minden 2-lsszefgg rszgrfjnak legalbb 2(k ; 1) le van. Bizonyts. Nzzk a fafelbonts dencijban szerepl F ft Minden F -beli e = (Vi Vj ) l V -t Se s V ; Se rszekre bontja. A fafelbonts miatt ebben a vgsban minden l Vi s Vj kztt megy. Mivel a Vi-k diszjunktak, ezrt az Se : e 2 F vgsok diszjunktak s szmuk k ; 1, ezrt minden 2-lsszefgg rszgrfnak legalbb 2(k ; 1) le van. 2.20 Ttel Az algoritmus sorn kapott blokkok G-nek egy fafelbontst adjk. Bizonyts. A T fban a blokkokat sszeh zva kapjuk az F ft Legyen (u v) egy

G ; T -beli l. Mivel az algoritmus mindig a legmlyebbre visszamen lt veszi, ezrt u s v vagy egy blokkban, vagy F -ben szomszdos blokkokban vannak. 2.21 Ttel Az algoritmus kiad egy H = (V E ) 2-lsszefgg rszgrfot, melyre jE j=jEoptj  3=2. A futsid O(E ) Bizonyts. Legyen a T fhoz hozzadott lek szma k Ekkor a 220 Ttel szerint G-nek ltezik egy k + 1 nagysg fafelbontsa. Mivel jT j = n ; 1, a 0 0 2.19 Ttelt felhasznlva n ; 1 + k  3=2: jE j=jEoptj  max( n 2k) 0 Seb , Szigeti s Cheriyan10] algoritmusa: Feltehet, hogy a G grf 2-pontsszefgg. Ellenkez esetben a 2-pontsszefgg komponensekben kln-kln alkalmazva az algoritmust, mindegyik komponensnek kapnnk egy 2-lsszefgg rszgrfjt. A rszgrfok unija G-nek egy 2-lsszefgg rszgrfjt adja, s az approximcis faktor legfeljebb akkora, mint a maximlis approximcis faktor a blokkokban. !gy az algoritmus sorn feltesszk, hogy G 2-pontsszefgg. Az algoritmushoz szksgnk lesz nhny

dencira s ttelre Egy G = (V E ) grf flfelbontsn utaknak olyan P0  P1 : : : Pk rendszert rtjk, melyekre k0 V (Pi) = V , P0 egypont trivilis t, s 8Pi 1  i  k 16 esetn a Pi t vgpontjai Vi 1 := V (P0)  V (P1) : : :  V (Pi 1)-ben vannak, de Pi-nek nincs bels pontja Vi 1 -ben. Ha egy Pi t kezd s vgpontja megegyezik (azaz a Pi kr), akkor Pi-t zrt flnek, ha a kt vgpontja klnbzik, akkor ny lt flnek nevezzk. Egy P0 + + P1 + : : : Pk flfelbonts ny lt (zrt), ha a P2 : : : Pk flek nyltak (zrtak). Egy fl hosszn a benne lv lek szmt rtjk. Egy flfelbonts pros (pratlan), ha a trivilis ton kvl minden t pros (pratlan) hossz . 2.22 Ttel (Whitney): (i) Egy grf pontosan akkor 2-lsszefgg, ha ltezik flfelbontsa. (ii) Egy grf pontosan akkor 2-pontsszefgg, ha ltezik nylt flfelbontsa. 2.23 Denci Legyen G egy 2-lsszefgg grf Jellje (G) G sszes flfelbontsban szerepl pros hossz flek minimlis szmt . Frank 11]-ben

megmutatta, hogy egy 2-lsszefgg grf (G) pros hossz flet tartalmaz flfelbontsa O(jV jjE j) lpsben megtallhat, s ha a grf 2-pontsszefgg is, akkor a flek nyltaknak is vlaszthatk. 2.24 Lemma Legyen G = (V E ) egy 2-lsszefgg grf Ekkor jEoptj jV j + (G) ; 1: Bizonyts. Kpzeljk el G egy G 2-lsszefgg rszgrfjt Ha G -nek ltezik olyan flfelbontsa, melynek (G)-nl kevesebb pros fle van, akkor ehhoz a flfelbontshoz hozzvve G leit mint 1 hossz fleket, G-nek olyan flfelbontst kapnnk, melynek (G)-nl kevesebb pros hossz fle lenne. Teht (G ) (G). Legyen P0 + P1 : : : + Pk a G egy flfelbontsa Az elzek miatt k (G). Ekkor jE j = k + jV j ; 1 (G) + jV j ; 1: Megjegyzs: Az elz lemma alapjn azonnal kaphatunk egy 1.5-szeres approximcit. Vegyk G-nek egy (G) pros hossz flet tartalmaz flfelbontst, s hagyjuk el az egy hossz fleket Legyen q a pratlan hossz flek bels pontjainak a szma. Ekkor a maradk grfban a pratlan hossz flek

ltal meghatrozott lek szma legfeljebb 3q=2, mg a pros hossz flek ltal meghatrozott lek szma legfeljebb (G) + jV j ; q ; 1. Az elz lemmt felhasznlva kapjuk, hogy a kapott grf lszma legfeljebb 15-szerese az optimumnak. ; ; ; 0 0 0 0 0 Ahhoz, hogy jobb approximcis faktort kapjunk, szksgnk lesz egy msik als becslsre is: 2.25 Lemma Legyen G = (V E ) egy 2-lsszefgg grf, s S  V S 6= ponthalmaz gy, hogy G ; S c 2 komponensre esik szt. Ekkor jEoptj jV j + c ; jS j: 17 Bizonyts. Nzzk G;S egy C komponenst Mivel minden 2-lsszefgg grfban minden C -beli pont foka legalbb 2, s C -bl megy ki l , ezrt C legalbb V (C ) + 1 szm llel jrul hozz az optimlis megoldshoz. A komponensekre sszegezve megkapjuk az lltst. Az algoritmus elszr megkeresi G-nek egy (G) pros hossz flet tartalmaz P0 + P1 : : : Pk nylt flfelbontst. Ezt a flfelbontst mdostva kap egy Q0 + Q1 : : : Qk flfelbontst az albbi tulajdonsggal: (i) a

flfelbontsnak (G) pros hossz fle van (ii) egy 3 hossz Qi fl bels pontja nem vgpontja egyetlen legalbb 2 hossz flnek sem (iii) nem ltezik l, ami egy 3 hossz Qi fl egy bels pontjt kti ssze egy msik 3 hossz Qj fl egy bels pontjval. 2.26 llts Ha adott egy G = (V E ) 2 lsszefgg grfnak egy P0 + P1 + + : : : + Pk nylt flfelbontsa, melynek (G) pros hossz fle van, akkor G-nek lineris idben meg tudjuk keresni egy tulajdonsg Q0 + Q1 : : : + + Qk flfelbontst. Bizonyts. Flszmra vonatkoz indukcival k = 1-re az llts trivilis. Tegyk fel, hogy az llts igaz P0 + P1 + : : : Pj 1 esetn. Legyen Pj = v1  v2 : : : vl  vl+1 egy l hossz nylt fl (azaz v1 s vl+1 a Pj vgpontjai, s v1 6= vl+1. Jellje T a Q0 + Q1 : : : + Qj 1 3 hossz fleinek a bels pontjainak a halmazt. Ha T v1 = s T vl+1 = illetve l = 1 akkor kszen vagyunk. Teht feltehet hogy l 2 1: eset: Pj -nek pontosan egy vgpontja van T -ben. Legyen Qi = w1 v1 w3 w4 egy v1 -t

tartalmaz 3 hossz fl. Ekkor legyen Qj = w4 w3 v1 : : : vl  vl+1, Qi -t pedig cserljl ki w1 v1 1 hossz lre. Mivel a mdosts sorn a pros hossz flek szmnak a paritsa nem vltozott, ezrt egy tulajdonsg felbontst kaptunk. 2: eset: Pj mindkt vgpontja T -ben van. Ha egy Qi = w1 v1 vl+1 w4 3 hossz fl tartalmazza mindkt vgpontot, akkor legyen Qj = w1 v1 v2 vl+1 w4, Qi helyett pedig vegyk a v1  vl+1 egy hossz flet. Az elz esethez hasonlan lthat, hogy egy tulajdonsg felbontst kaptunk. Ha v1 egy Qi = w1 v1 w3 w4-ben, vl+1 egy Qh = z1  vl+1 z3  z4 flben van benne, akkor legyen Qj = w4 w3 v1 : : : vl+1  z3 z4 , Qi -t cserljk ki a w1 v1 lre, Qh-t pedig a z1 vl+1 lre. !gy megint egy tulajdonsg felbontst kaptunk. Az algoritmus miutn G-nek megtallja egy tulajdonsg flfelbontst, elhagyja az 1 hossz fleket. Legyen az gy kapott grf G = (V E ) A 2.22 Ttel alapjn G 2-lsszefgg ; ; 0 0 18 0 Jellje T a 3 hossz flek bels

pontjait. Az tulajdonsg miatt G T ]-ben minden sszefgg komponens 2 pont . 2.27 Lemma jEopt j 3jT j=2: Bizonyts. Alkalmazzuk a 225 Lemmt S = V ; T s c = c(G ; S ) = = jT j=2-re. 2.28 Ttel Az elzekben lert algoritmus egy G = (V E ) 2-lsszefgg grfnak megtallja egy G = (V E ) 2-lsszefgg rszgrfjt gy, hogy jE j  17=12: Az algoritmus futsideje O(nm). jEoptj Bizonyts. A 224 Lemma s az 227 Lemma miatt jEopt j max(n + (G) ; 1 3jT j=2). A 3 hossz flekben lv lek szma 3jT j=2. A 2 hossz s a legalbb 4 hossz flekben lv lek szma  (G) + 5(n ; t ; 1)=4. Ezekbl addik, 0 0 0 hogy 1 jE j  jT j 2 + 5(n + (G) ; 1) jEoptj 4 3jT j 4 n + (G) ; 1 = 17=12: 0 k-l sszef gg sg Khuller s Raghavachari 7] algoritmusa: Elszr pros k-ra ismertetjk az algoritmust. Az algoritmus fzisokbl ll. Egy fzison bell az sszefggsget 2-vel nveljk k=2 fzis utn kapunk egy S k-lsszefgg rszgrfot Az i: fzis elejn S (2i ; 2)-szer lsszefgg, a fzis vgn

2i-szer lsszefgg lesz. Elszr mlysgi keresssel hozzadjuk S -hez G ; S egy maximlis Fi erdjt. Ez az sszefggsget 2i ; 1-re fogja nvelni 2.29 Denci Legyen e = (u v) az Fi erd egy le, dfs(u)<dfs(v) Az e lt fed legmlyebb visszalnek olyan G ; S ; Fi-beli lt neveznk, melynek egyik vgpontja v-nek utda, a msik vgpontja pedig u-nak se, s dfs(u) minimlis. Ezutn Fi leit fordtott sorrendben nzzk vgig, mint ahogy a mlysgi keress megtallta ket. Minden alkalommal amikor tallunk egy (u v) 2 Fi lt gy, hogy S -ben u-bl v-be nincsen 2i darab lidegen t, akkor S -hez hozzvesznk G ; S -bl egy e-t fed legmlyebb visszalt. 19 Miutn Fi minden lt megvizsgltuk, S 2i-szer lsszefgg lesz. Megmutatjuk, hogy az algoritmus ltal kiadott grf lszma legfeljebb (3+ ln2)=2 1:85-szrse az optimumnak. Elszr megmutatjuk hogy a kapott grf k-szor lsszefgg. 2.30 Lemma Legyen G = (V E ) egy legalbb k-szor lsszefgg grf Legyen S egy k ; 1-szer

lsszefgg rszgrfja G-nek, F pedig G ; S -ben egy maximlis erd. Ekkor S  F k-szor lsszefgg Bizonyts. Tegyk fel indirekt, hogy S  F nem k-lsszefgg Mivel S (k ; 1)-szer lsszefgg, ez azt jelenti,hogy S  F -bl el lehet hagyni k ; 1 lt, hogy a maradk grf C1  : : : Cl l 2 komponensre esik szt. Mivel F maximlis erd volt, ezrt E ; (S  F )-ben a komponensek kzt nem mehet l, ami azonban ellentmond annak, hogy G k-lsszefgg. 2.31 Lemma Legyen G = (V E ) egy legalbb k-lsszefgg grf Legyen S egy (k ; 2)-szer lsszefgg rszgrfja G-nek, melyet egy F maximlis erd hozzadsval (k ; 1)-szer lsszefggv tettnk. Vegynk E ; (S  F )bl egy B lhalmazt gy, hogy brmely kt, F -ben szomszdos pont kztt S  F  B -ben ltezzk k darab ldiszjunkt t. Ekkor S  F  B k-lsszefgg Bizonyts. Indirekt tegyk fel, hogy ltezik S  F  B -ben egy k ; 1 nagysg C lhalmaz, amelyre (S  F  B ) ; C C1 : : : Cl l 2 komponensekre esik szt. Kpzeljk el

F egy T fjt A felttel szerint T brmely 2 szomszdos pontja kztt ltezik S  F  B -ben k lidegen t  ebbl kvetkezik hogy brmely 2 T -beli pont kztt ltezik S  F  B -ben k lidegen t. !gy F minden T fja valamelyik Ci komponensbe esik, ezrt a C1 : : :  Cl komponensek kztt G ; (S  F  B )-ben nem vezethet l, hiszen F maximlis erd volt. Ekkor azonban C egy k ; 1 l vgs lenne G-ben, ami ellentmond annak, hogy G k-szor lsszefgg. 2.32 Ttel A fentiekben ismertetett algoritmus egy k-szor lsszefgg rszgrfjt adja G-nek. Bizonyts. i-re vonatkoz indukcival beltjuk, hogy az i: fzis befejezse utn S 2i-szer lsszefgg. i = 0-ra trivilis. Az indukcis feltevs szerint az i: fzis megkezdsekor S (2i ; 2)-szer lsszefgg. Az algoritmus ezutn hozzad S -hez egy maximlis DFS erdt. A 230 Lemma alapjn gy S (2i ; 1)-szer lsszefgg lesz Ezutn az algoritmus visszalek hozzdsval elri, hogy a DFS erd brmely kt szomszdos pontja kztt vezessen

S -ben 2i lidegen t. A 231 Lemma 20 miatt gy S 2i-szer lsszefggv vlik. Teht k=2 fzis utn S k-lsszefgg lesz. Most rtrnk annak a bizonytsra, hogy S lszma legfeljebb 1:85szrse az optimumnak. Nzzk az algoritmus i: fzist. Ez hozzad S -hez egy Fi DFS erdt, majd visszaleknek egy Bi halmazt. Minden eb 2 Bi l azrt kerl be S -be, hogy lefogja valamely ef 2 Fi l ltal induklt 2i ; 1-s vgst. Minden eb 2 Bi-re jellje c(eb ) ezt az egyrtelmen meghatrozott Fi-beli lt, s legyen c(Bi) := eb Bi c(eb). Mivel Bi s c(Bi) elemei kzt ltezik egy bijekci, ezrt elemszmuk megegyezik. Legyen fi = jFij s bi = jBij 2 2.33 Lemma Minden i fzisra jOPT (G)j (k ; 2i + 2)bi Bizonyts. Tekintsk az algoritmus i: fzist Legyen e = (x y) 2 Fi, ahol x az y szlje. Meggyelhetjk, hogy ha e = c(eb ) valamely eb 2 Bi-re, akkor a fzis kezdetekor x s y kztt 2i ; 2 lidegen t volt S -ben, a fzis befejeztekor pedig 2i. Legyen C egy 2i ; 1 lbl ll vgs S 

Fi-ben, amely szeparlja x-t s y-t. Legyen C -nek az S  Fi-bl trtn elhagysa utn keletkez 2 komponens X s X , x 2 X , y 2 X . Mivel a fzis kezdetekor S (2i;2)-szer lsszefgg, gy Fi -nek csak az (x y) le van benne C -ben. Jelljk Pe-vel azon G ; (S  Fi )beli leket, melyek egyik vgpontja X -ben, msik vgpontja X -ben van 0 0 0 2.34 Lemma Pe pontosan azon G ; (S  Fi )-beli lekbl ll, melyek y valamely leszrmazottjt ktik ssze x valamely svel. Bizonyts. Ha y valamely leszrmazottja X -ben volna, akkor Fi -nek az (x y) len kvl mg legalbb egy eleme benne lenne C -ben, de az elbb lttuk, hogy ez lehetetlen. Hasonlan addik, hogy az y-t tartalmaz fa minden olyan pontja, amelyik nem leszrmazottja y-nak, X -ben van Tovbb Fi minden ms T fja vagy X -ben, vagy X -ban van. Mivel Fi -ben nincs keresztl, ezrt a fentiek miatt egy X s X kzti l y egy leszrmazottjt kti ssze x egy svel. Pe dencija miatt G-nek minden k-lsszefgg rszgrfja

legalbb k ; ; 2i + 2 lt tartalmaz Pe-bl. Elegend teht beltni, hogy e 2 Bi -re a Pe vgsok diszjunktak. Legyen l 2 Bi, l 2 Bi kt visszal, melyeket az algorimus az e = (u v) s e = = (x y) falek megvizsglsa sorn adott hozz a megoldshoz. Feltehetjk, hogy az algoritmus az e lt vizsglta t elbb. 1. eset: e benne van az Fi-ben v-bl r-be men ton Pe Pe 6= azt 0 0 0 0 0 0 21 jelenten, hogy ltezik e-t s e -t fed visszal, de mivel l egy legmlyebbre men e-t fed visszal volt, ezrt ekkor l fedn e -t is, aminek kvetkeztben l -re mr nem is lett volna szksgnk. Teht ebben az esetben Pe Pe = 2. eset: e nincs benne van az Fi -ben v-bl r-be men ton Mivel Fi-ben nincsenek keresztlek, ezrt Pe Pe = . 0 0 0 0 0 0 2.35 Ttel Az algoritmus ltal adott grf lszma legfeljebb 1:85-szrse az optimumnak. A lpsszm O(k2jE j2) Bizonyts. A ttelt pros k-ra ltjuk be (pratlanra egy kis mdostssal ugyangy megy a bizonyts) Az algoritmus az i:

fzisban fi + bi j lt vesz. Mivel Fi s Bi is erdk, ezrt fi < n s bi < n Felhasznlva a 233 Lemmt, illetve a trivilis jOPT j kn=2 egyenltlensget, az addik, hogy P Pk=i=12 (fi + bi) 4b 3kn=4 + k= i 1 i  jOPT (G)j maxfkn=2 maxif(k ; 2i + 2)bigg X ; X k=4 k=4 3 1 3 1  2 + k ; 2i + 2  2 + 2 k=2 ;1 i + 1  23 + ln22 < 1:85: i=1 i=1 Egy iterciban elszr egy max. erdt vesznk Ez O(jE j) lpst jelent Annak eldntse, hogy egy l 2 vgpontja kztt ltezik-e 2i diszjunkt t, O(kjE j) lpsben megtehet. Egy fzison bell teht a lpsszm O(kjE j2) Mivel k=2 fzis van, gy az sszlpsszm O(k2jE j2). 2.22 S lyozott l sszef gg sg Az ltalnos esetben adott egy G = (V E ) k-lsszefgg irnytatlan grf, lein nemnegatv s lyokkal. A feladat az, hogy talljunk G-nek egy minimlis s ly k-lsszefgg H rszgrfjt. k = 2-re Frederickson s Jj 1981-ben adott egy 3-szoros approximcit. Az algoritmus az els fzisban keres egy minimlis s ly feszt ft A

msodik fzisban a ft kiegszti lekkel, hogy 2 lsszefgg grfot kapjunk. Tetszleges k-ra Khuller s Vishkin 3]-ban adott egy 2-szeres approximcit. Az algoritmus: minden e = (u v) irnytatlan lt helyettestsnk (u v) s (v u) irnytott lekkel, s a s lyuk legyen w(e). Jellje D az gy kapott irnytott grfot. Jelljk ki D valamely r pontjt, s keressnk Dben egy minimlis s ly rszgrfot, melyben minden ponthoz vezet r-bl k ldiszjunkt t. Edmonds 20]-ban megmutatta, hogy ez a feladat polinomilis idben megoldhat. Ha az (u v) s (v u) irnytott lek kzl legalbb az egyiket kivlasztottuk, akkor az (u v) irnytatlan lt hozzadjuk EH -hoz. 22 2.36 Lemma A H = (V EH ) grf k-lsszefgg rszgrfja G-nek Bizonyts. Tegyk fel, hogy ltezik k ; 1 l, melyeket elhagyva a grf 2-nl tbb komponensre esik szt. Ekkor azonban r-bl egy olyan pontba, amelyik nem az r pontot tartalmaz komponensbe esik, D-ben nem mehet k ldiszjunkt t. Teht H valban

k-lsszefgg 2.37 Ttel EH s lya legfeljebb 2-szerese az optimumnak Bizonyts. Legyen OPT egy minimlis s ly k-lsszefgg rszgrfja Gnek OPT leit 2 ellenttes irnyts llel helyettestve D-nek egy rszgrfjt kapjuk, melynek s lya 2w(OPT ). Tovbb a kapott grfnak megvan az a tulajdonsga, hogy minden pontba ltezik r-bl k darab lidegen irnytott t. Mivel az algoritmus a minimlis ilyen tulajdonsg rszgrfot tallja meg, ezrt w(EH )  2w(OPT ). 3. IRNYTOTT GRFOK Minimlis s ly k-lsszefgg rszgrf keressre a kvetkez egyszer 2 approximci ismert: vegynk egy tetszleges s pontot, s Edmonds 20] algoritmusval hatrozzunk meg egy F1 illetve F2 olyan minimlis s ly rszgrfokat, hogy F1 -ben s-bl minden pontba ltezik k ldiszjunkt t, s F2-ben minden pontbl ltezik s-be k ldiszjunkt t. F1  F2 k-szor lsszefgg grf lesz, melynek s lya legfeljebb 2-szerese az optimumnak. S lyozatlan esetben k 2 esetn sokig csak az elz 2-szeres approximci volt

ismert. Cheriyan s Thurimella adott elszr 5]-ben 2-nl jobb approximcit. Az algoritmusuk ugyan gy mkdik mint az irnytatlan esetben hasznlt algoritmus, s pontsszefggsg esetn 1+1=k approximp cit, lsszefggsg esetn 1 + 4= k approximcit ad. S lyozatlan esetben k = 1 esetre Khuller, Raghavachari 12]-ben s Young adott egy 1:64 faktoros approximcit, amit az algoritmus kis mdostsval 13]-ban 1:61-re javtottak. Az algoritmust a fejezet els rszben ismertetjk A fejezet sorn csak a s lyozatlan esettel foglalkozunk. 3.1 Ers sszefggsg Ebben a rszben Khuller, Raghavachari s Young 1:61 faktor approximcis algoritmust ismertetjk minimlis lszm ersen sszefgg rszgrf keressre. Az algoritmus krket h z ssze egszen addig, mg egy olyan H grfot kap, melyben nincs hromnl hosszabb irnytott kr. Beltjuk, hogy egy ilyen 23 grfnak polinomilis idben meg tudjuk keresni egy minimlis lszm ersen sszefgg rszgrfjt. Az algoritmus az

sszeh zott leket s H egy minimlis lszm ersen sszefgg rszgrfjt adja ki 3.1 Ttel Legyen G = (V E ) egy olyan ersen sszefgg irnytott grf, melyben minden irnytott kr legfeljebb 3 hossz . pEkkor G-nek egy minimlis lszm ersen sszefgg rszgrfja O(n2 + m n) idben megtallhat, ahol n, m G pont- illetve lszma. Bizonyts. Feltehetjk, hogy G irnytatlan rtelemben 2-szer pontsszefgg, azaz nincs elvg pont. 3.2 Denci Az e 2 E l kritikus, ha G ; e nem ersen sszefgg Az e 2 E l lnyegtelen, ha G ; e ersen sszefgg. Az e = (u v) l veszlyes, ha nem ltezik kritikus lekbl ll v ! u t. 3.3 Lemma Minden lnyegtelen l pontosan egy krben van benne Bizonyts. Tegyk fel indirekt, hogy egy (u v) lnyegtelen l legalbb kt krben van benne. Ekkor v s u kztt legalbb kt t ltezik Mivel nincs hromnl hosszabb kr a grfban, ezrt valamelyik t pontosan 2 hossz . Legyen ez az t (v x u). Mivel (u v) lnyegtelen, ezrt u s v kztt

ltezik egy legalbb 2 hossz irnytott Puv t. A Puv tnak t kell mennie az x ponton, klnben Puv s (v x u) egy legalbb 4 hossz krt alkotna. Ha (v u) 2 E akkor Puv pontosan 2 hossz , azaz Puv = (u x v). Ebben az esetben teht az x, u, v pontok kztt mind a hat lehetsges l szerepel. Jellje Vv a v pontbl az u s x pontok felhasznlsa nlkl elrhet pontokat. Hasonlan denilhatjuk a Vu s Vx halmazokat. Mivel G ersen sszefgg s nincs benne hromnl hosszabb kr, ezrt ezek a halmazok diszjunktak s legalbb az egyik nem res. Ekkor azonban az u v x pontok kzl legalbb az egyik elvg pont lenne, ellentmondva a feltevsnek. Teht (v u) 62 E s ltezik egy (v y u) t is. A Puv tnak t kell mennie az y ponton is, mert klnben Puv s (v y u) egy legalbb 4 hossz kr lenne. A Puv t teht tmegy az x s az y ponton is, ezrt x s y esetleges felcserlse utn ltezik egy Q x ! y t, ami nem hasznlja az (u v) lt. Ekkor Q, (y u), (u v) (v u) egy legalbb 4

hossz krt alkotna. 3.4 Lemma G = (V E ) E  E ersen sszefgg , E tartalmazza a kritikus leket, s minden (u v) 2 E veszlyes lre G -ben v-bl u-ba ltezik olyan t, amely kritikus lekbl s egy darab lnyegtelen lbl ll. 0 0 0 0 0 24 Bizonyts. ) A 33 Lemma miatt egy krben legfeljebb egy lnyegtelen l szerepelhet. Ezt felhasznlva a felttel szksgessge azonnal kvetkezik ( G ersen sszefggsghez elegend beltni, hogy minden (u v) 2 E lre G -ben ltezik v ! u t. A felttel szerint azonban ilyen t ltezik A 3.4 Lemma alapjn a feladat a kvetkez problmra redukldik: keressnk minimlis elemszm , lnyegtelen lekbl ll M lhalmazt, hogy minden veszlyes (u v) lre ltezzen kritikus lekbl s egy darab M -beli lbl ll v ! u t. Ksztsnk egy irnytatlan G segdgrfot: G pontjai legyenek G veszlyes lei. Minden e lnyegtelen lre, (i) ha e benne van egy 2 hossz krben melynek a msik le veszlyes, akkor ezen lnek G -ben megfelel pontra

tegynk egy huroklt (ii) ha egy 3 hossz krben van benne melynek az egyik le veszlyes, akkor ezen veszlyes lnek G -ben megfelel pontra tegynk egy huroklt (iii) ha egy 3 hossz krben van benne melynek a msik kt le veszlyes, akkor G -ben ezen kt pont kztt vegynk egy let. Mivel minden lnyegtelen l pontosan egy krben van benne, ezrt minden lnyegtelen lnek legfeljebb egy G -beli l felel meg. A 3.4 Lemma alapjn G -ben egy lhalmaz pontosan akkor fedi G pontjait ha az leknek megfelel lnyegtelen lek a kritikus lekkel egytt ersen sszefgg rszgrfot hatroznak meg. Teht a feladat egy minimlis lfedsre egyszersdtt, ami ekvivalens egy maximlis prosts megtallsval. 3.5 llts G pros grf Bizonyts. Beltjuk, hogy G veszlyes lei 2 sznnel sznezhetk, hogy a szomszdos lek klnbz sznek. Ebbl az llts azonnal kvetkezik Ha a veszlyes leknek nem lenne j sznezse, akkor veszlyes lekbl lenne egy pratlan C kr. Legyen (a b) a kr egy

le Megmutatjuk, hogy ltezik egy msik a ! b t is, azaz az (a b) l lnyegtelen. Mivel lnyegtelen l nem lehet veszlyes, gy ellentmondst kapunk. Elegend megmutatni, hogy a C kr minden ms (u v) lre ltezik egy v ! u t amelyik nem hasznlja az (a b) let. Ha a C kr egy (u v) lre egy v ! u t tartalmazza az (a b) let, akkor ez az t 2 hossz , s vagy v = a vagy u = b. Nzzk az els esetet ( a msik hasonlan megy) A (b u) l nem lehet lnyeges, mert ekkor az (a b) l nem lenne veszlyes. (b u) teht lnyegtelen, ezrt ltezik egy msik Pbu t. Ennek az tnak t kell mennie a v ponton, mert klnben Pbu s az (u a) illetve (a b) lek egy legalbb 4 hossz krt alkotnnak. A Pbu tnak teht ltezik egy (a b) let nem hasznl v ! u rsz tja, amint azt lltottuk. G -t O(n2) lpsben meg lehet konstrulni, pros grfban egy maximlis p prostst O(m n) lpsben meg lehet tallni. Ezzel belttuk, hogy ha G0 0 0 0 0 0 0 0 0 0 0 0 25 ben nincs hromnl

hosszabb kr,pakkor G-nek egy minimlis lszm ersen sszefgg rszgrfjt O(n2 + m n) idben megtallhatjuk. Ezek utn rtrnk az algoritmus ismertetsre, mely a minimlis ersen sszefgg rszgrf problmra 1.61 faktor approximcit ad 3.6 Ttel Minden c > 2=6 ; 1=36 1:61 szmra ltezik egy c approximci a minimlis ersen sszefgg rszgrf problmra Bizonyts. Az algoritmus a kvetkez: legyen k 4 egy rgztett pozitv egsz. Amg a grfban ltezik legalbb k hossz kr, addig h zzunk ssze egyet. Ha a grfban mr nem ltezik legalbb k hossz kr, akkor kezdjk el sszeh zni a k ; 1 hossz krket stb. Ha az sszeh zsokkal eljutunk egy olyan grfhoz, melyben nincs hromnl hosszabb kr, akkor ennek a grfnak hatrozzuk meg egy minimlis lszm ersen sszefgg H rszgrfjt. Az algoritmus az sszeh zott leket s a H grfot adja vissza. Vilgos hogy az algoritmus ltal adott rszgrf ersen sszefgg Rgztett k-ra egy legalbb k hossz krt legfeljebb O(mk ) lpsben

meg tudunk keresni, gy az algoritmus rgztett k-ra polinomilis, s legfeljebb O(nmk+1) lpst tesz. 3.7 Lemma Ha egy n pont G irnytott grfban a leghosszabb kr l hossz , akkor G minden ersen sszefgg rszgrfjnak legalbb (n ; 1)l=(l ; 1) le van. Bizonyts. Minden ersen sszefgg grf egy pontt h zhat krk egyms utni sszeh zsval Egy sszeh zs sorn az sszeh zott lek s a pontok cskkensnek arnya legalbb l=l ; 1. Mivel a pontok szma sszesen n ; 1-gyel cskken, ezrt egy ersen sszefgg grfnak legalbb (n ; 1)l=(l ; 1) le van. Jellje n a grf pontszmt, ni pedig a legalbb i hossz krk sszeh zsa utn megmarad grf pontszmt (i = 4 : : : k). Legyen H az az sszeh zsok utn keletkez grf, melyben mr nincs hromnl hosszabb kr, s jellje OPT (H ) ennek egy minimlis ersen sszefgg rszgrfjt. Az algoritmus ltal vett lek szma legfeljebb k (n ; n ) + k 1 i (n ; n ) + jopt(H )j: k i+1 i k;1 i=4 i ; 1 Felhasznlva, hogy jopt(H )j  2(n4 ;1)

s a fenti kifejezst talaktva kapjuk, hogy az algoritmus ltal adott lek szma legfeljebb k (n ; 1) + k ni ; 1 + 1=3jopt(H )j: k;1 i=5 (i ; 1)(i ; 2) X ; X 26 A 3.7 Lemma miatt 8i-re jOPT (G)j (ni ; 1)(i ; 1)=(i ; 2), tovbb jopt(H )j  jopt(G)j miatt az approximcis faktor legfeljebb k k +X 1 + 1=3  2 ; 1 + 1 : k ; 1 i=5 (i ; 1)2 6 36 k(k ; 1) Az algoritmus lpsszma annyiban fgg c-tl, hogy c mennyire van kzel 1.61-hez (azaz a fenti kplet szerint k-t milyen nagyra kell vlasztani) 3.2 Tbbszrs sszefggsg Cheriyan s Thurimella 5] algoritmusa pontsszefggsg esetn: Az algoritmus a kvetkez: az els fzisban egy minimlis nagysg M  E lhalmazt keresnk, melyre 8v 2 V pontra %M (v) (k ; 1) s M (v) (k ; 1). A msodik fzisban a 24 Ttelben hasznlt mdon egy tartalmazsra nzve minimlis F  E ; M lhalmazt vesz gy, hogy M  F k-pontsszefgg legyen. Az els fzisban M -t a kvetkezkppen kaphatjuk meg: ksztsnk G-bl egy irnytatlan, pros B (G)

grfot. Minden v 2 V pont helyett vegynk kt, v s v+ pontot, s egy (u v) 2 E irnytott lnek feleltessk meg B (G)-ben az (u+ v ) irnytatlan lt. Ekkor 8v 2 V esetn %M (v) (k ;1) s M (v) (k ; 1) , dB(M ) (z) (k ; 1) minden B (G) -beli z pontra: Azaz M megtallshoz B (G)-ben egy b-prostst kell megoldanunk. 3.8 Denci Egy irnytott grfban egy pros hossz krt alternl krnek hvunk, ha az egymst kvet lek fordtott irnyts ak Egy C alternl kr egy v pontja C -ki (C -be) pont, ha C -ben van kt egymst kvet, v-bl kimen (v-be bemen) l. Bizonyts nlkl hasznlni fogjuk Mader 21]-beli ttelt. 3.9 Ttel : Egy k-pontsszefgg irnytott G grfban egy kritikus lekbl ll alternl krben vagy ltezik C -ki pont, melynek G-beli kifoka k, vagy ltezik egy C -be pont, melynek G-beli befoka k. Az albbi llts knnyen lthat: 3.10 llts Legyen G egy irnytott grf, B (G) pedig a belle a fenti mdon ksztett pros grf. G-ben pontosan akkor ltezik

alternl kr, ha B (G)-ben ltezik kr. ; ; 3.11 Lemma Legyen F  E ; M az algoritmus ltal a msodik fzis sorn megtallt kritikus lek halmaza. Ekkor jF j  2jV j ; 1: 27 Bizonyts. Legyen G = (V M  F ) lltjuk hogy G -ben nincs alternl 0 0 kr. Egy C alternl krnek ugyanis minden C -ki pontjnak G -ben legalbb k+1 a kifoka, s minden C -be pontnak legalbb k+1 a befoka, ami ellentmond a 3.9 Ttelnek A 310 llts miatt gy B (G) aciklikus, ezrt jF j  2jV j; 1: 0 3.12 Ttel Legyen G = (V E ) egy k-pontsszefgg irnytott grf A fenti algoritmus megtall egy (V E ) k-pontsszefgg rszgrfot, amelyre lszm k-pontsszefgg jE j  (1+1=k)jEoptj, ahol (V Eopt ) egy3 minimlis 2 1 : 5 rszgrf. Az algoritmus futsideje O(k jV j +)E j (log jV j)2) Bizonyts. Legyen M  E (B (Gopt )) olyan minimlis szm lhalmaz, hogy dM (v) k ; 1 minden B (G)-beli pontra. Mivel M olyan minimlis elemszm lhalmaz volt, hogy B (G)-ben minden pontra dM (v) (k ; 1) teljeslt,

ezrt jM j  jM j. A 23 Ttelt M -ra s B (Gopt)-ra alkalmazva jM j  jE (B (Gopt))j ; jV (B (Gopt ))j=2 = jEoptj ; jV j. Felhasznlva, hogy jF j  2jV j ; 1, s jEopt j kjV j kapjuk, hogy 0 0      jE j  jEoptj ; jV j + 2jV j ; 1  1 + 1=k: jEoptj jEopt j 0 Abban az esetben, ha a G = (V E ) irnytott grf k-lsszefgg, s egy minimlis lszm k-szor lsszefgg rszgrfjt keressk, Cheriyanps Thurimella 5]-ben az elzvel azonos elv algoritmust adott, mely 1 + 4= k approximcit ad. Az algoritmus a kvetkez: az elz algoritmushoz hasonlan, az els fzis sorn egy olyan minimlis lszm M halmazt keresnk, hogy minden v pontra %M (v) k s M (v) k: Nyilvnvalan jM j  jEoptj. A msodik fzis sorn egy tartalmazsra nzve minimlis F lhalmazt vesz, melyre M F k-szor lsszefgg. Az algoritmus az M  F grfot adja ki 3.13 Ttel Legyen G = (V E ) egy k-szor lsszfgg irnytott grf A fenti algoritmus G-nek p megtallja egy (V E ) k-szor lsszfgg

rszgrfjt, melyre jE j  (1 + (4= k))jEoptj, ahol jEoptj egy minimlis lszm k-szor lsszfgg rszgrf lszma. A futsid O(k3jV j2 + jE j1:5(log jV j)2) Bizonyts. Szksgnk lesz a kvetkez dencira: 3.14 Denci Egy k-pontsszefgg irnytott grf egy (u v) lt specilisnak hvjuk, ha az (u v) l kritikus s (u) k + 1, %(v) k + 1: Vilgos, hogy a G = (V M  F ) grfban minden F -beli l specilis. 0 0 0 28 3.15 Ttel (Cheriyan, Thurimella 5]) Egy n pont p k-lsszefgg ir- nytott H grfban a specilis lek szma legfeljebb 4n k: Jellje V a H grf ponthalmazt. Minden specilis e lhez ltezik egy Ae  V halmaz, hogy e 2 (Ae), j(Ae)j = k, s 2  jAej  n ; 2 (ha tbb is ltezik akkor vegyk az egyiket). Jellje Fki az ezen halmazokbl ll halmazrendszert, azaz Fki = fA1 A2 : : : Al g olyan halmazrendszer, hogy minden i-re (Ai ) = k, (Ai) tartalmazza valamely specilis let, s minden specilis l benne van valamelyik (Ai)-ben. A szoksos

kikeresztezs utn kapunk egy ugyanilyen tulajdonsg laminris halmazrendszert, jelljk ezent l ezt Fki-vel. Az ismert mdon az Fki  V halmazon denilhatunk egy irnytatlan gykeres T ft: Ai s Aj kztt vezessen egy l, ha Aj a legszkebb Ai -t tartalmaz Fki  V -beli halmaz (vagy fordtva). Az egyszersg kedvrt az Ai-hez tartoz T -beli pontot szintn Ai-vel jelljk Legyen i = = fAin  A 2 Fki : A  Ai  A 6= Aig. Jellje tovbb R2 azon A 2 Fki halmazokat, melyeknek T -ben pontosan kt szomszdjuk van, s legyen R1 = = fA : A 2 FkinR2 g: 3.16 llts jR1j  2jV1j=(k + 1), ahol V1 =  i : Ai 2 R1 Bizonyts. Legyen T1 az fa, amelyiket T -bl kapjuk az albbi mdon: bontsuk fel T -t olyan A0  A1 : : : Aq  Aq+1 utakra, hogy 1  i  q esetn Ai foka T -ben kett (azaz Ai 2 R2 ), s A0 2 R1 , Aq+1 2 R1 . Minden ilyen tnl trljk el T -bl az A1 : : : Aq pontokat s a bellk indul leket, tovbb h zzuk be az A0  Aq+1 lt. Jellje az gy kapott ft T1. T1 pontjai az R1

-beli halmazok s V lesz, s T1 -ben minden nem levl R1 -beli halmaz foka legalbb 3. Ha a T1 -beli levelek szmt l1 -gyel jelljk, akkor az elz megjegyzs miatt jR1 j  2l1 . Mivel minden tartalmazsra nzve minimlis Ai 2 Fki halmaz kifoka pontosan k, s Ai tartalmaz olyan pontot, melynek kifoka k + 1 (hiszen Ai-bl megy ki specilis l), ezrt egyszer szmolsal lthat, hogy jAij k + 1. Ezt felhasznlva jR1j  2jV1j=(k + 1). A specilis leket a kvetkezkppen szmoljuk meg: Legyen Ai Aj egy l T1 -ben (Ai  Aj ). Ha ez az l mr a T fban is benne volt, akkor az Ai  Aj l szmolja az Ai-bl s Aj -bl kimen specilis leket. Ezen lek szma legfeljebb 2k. Ha az Ai Aj l egy Ai A1  : : : Aq  Aj t mdostsa miatt jtt ltre, akkor az Ai Aj l szmolja Ai -bl s Aq -bl kimen specilis leket. Az ilyen lek szma legfeljebb 2k !gy a T1 fa lei ltal megszmolt kritikus lek szma legfeljebb 2kjR1 j. A fennmarad kritikus lek valamely "mdostott ton

bell" mennek. Pontosabban: legyen P = A0 A1 : : : Aq  Aq+1, A0  A1 : : :  Aq+1 olyan T -beli 29 t, hogy Ai 2 R2 1  i  q, s A0 62 R2, Aq+1 62 R2. Legyen VP = = 1  2 : : : q. Egy ilyen tnl azon (v w)specilis leket nem szmoltuk meg a T1 fa leivel, melyekre v 2 VP s (v w) 2 f (Ai) : 1  i  q ; 1g.  p lltjuk, hogy az ilyen lek szma legfeljebb kjVP j. Rendezzk a VP pontjait sorba gy, hogy a i-beli pontok a sorrendben megelzzk a i+1beli pontokat. Tetszleges v 2 VP ponta jelle ;v azon w pontok halmazt, melyekre w 2 VP s (v w) 2 f (Ai ) : 1  i  q ; 1g. Legyen a ;v -beli pontok sorrendje w1 : : : w;v . p Egy (v wj ) lt rvid lnek hvunk, ha j  k, egybknt p pedig hossz lnek hvjuk. Vilgos, hogy a rvid lek szma legfeljebb kjVP j Egy (v wj ) hossz lt "szmoljuk meg p a w1 : : : w k 2 ;v pontoknl, azaz ezeket a pontokat s lyozzuk meg 1= k-val. !gy a VP -beli pontok sszs lya egyenl a hossz lek szmval. Legyen wa 2 i 1  i  q ;

1 egy tetszleges pont. Ezt a pontot csak ap (Ai p1 ) lek miatt s lyozhattuk meg, ezrt az wa pont s lya legfeljebb k k = k. A hossz lek szma teht legfeljebb p kjVP j.  p ; Azt kaptuk teht, hogy egy tetszleges fenti tulajdonsg p P tnl a T1 fa lei ltal nem szmolt specilis lek szma legfeljebb 2 kjVP j. A fent lertak miatt a G-beli specilis lek szma legfeljebb p p 1 2kjR1j + 2 kn2  k4kn + 2 kn2 +1   ahol n1 = j i : Ai 2 R1 j s n2 = j i : Ai 2 R2 j. A fenti kifejezs akkor maximlis, ha n2 a lehet legnagyobb. Mivel T -ben legalbb kt levl van, ezrt n2  n ; (2k + 2). Ezrt a specilis lek szma legfeljebb p p 4k(2k + 2)=(k + 1) + 2 k(n ; (2k + 2))  4 kn: p Mivel az algoritmus ltal vett F -beli lek specilisak, ezrt jF j  4n pk. Mivel jM j  jEoptj, ezrt azonnal addik, hogy a fenti algoritmus egy 1+4 k approximci. 30 4. LTALNOSTOTT STEINER FELADAT Ebben a fejezetben egy irnytatlan grfnak keressk minimlis s ly rszgrfjt mely

minden vgsbl legalbb elre megadott szm let tartalmaz. Pontosabban fogalmazva: Adott egy irnytatlan grf G = (V E ), egy f : 2V ! Z halmazfggvny, s egy c : E ! Q + nemnegatv s lyfggvny. Oldjuk meg az albbi IP feladatot: (1) min cexe X e E 2 8S  V : x((S )) f (S ) 8e 2 E : xe 2 f0 1g A fenti feladat fontos specilis esete az un. ltalnostott Steiner feladat: minden i j pontprra adott egy rij igny s minimlis s ly rszgrfot kell tallni melyben minden i j pontpr kztt ltezik rij ldiszjunkt t. Ha r  k akkor az ltalnostott Steiner feladat specilis eseteknt a minimlis s ly k-lsszfgg rszgrf problmt kapjuk. 0 1 rtk j fggvnyekre 14]-ben Goemans s Williamson adott egy 2 faktor priml-dul algoritmust. Goemans, Williamson, Mihail s Vazirani 22]-ben tetszleges j fggvnyre adott 2fmax faktor priml-dul algoritmust. Nem sokkal ksbb Goemans, Goldberg, Plotkin, Shmoys, Tardos s Williamson 15]-ben ltalnostottk az algoritmust

ferdn szupermodulris fggvnyekre, s az algoritmus mdostsval az approximcis faktort 2 (fmax ) -ra javtottk. Ferdn szupermodulris fggvnyekre Kamal Jain 16]-ban adott 2 approximcit. Az algoritmusa iteratve megoldja az IP relaxcijt, majd kerekti a megoldst Az algoritmusok ismertetse sorn a kvetkez dencikat s egyszer lltsokat fogjuk hasznlni. 4.1 Denci Egy f : 2V ! Z fggvny ferdn szupermodulris, ha 8A B  V halmazra f (A) + f (B )  maxff (A ; B ) + f (B ; A) f (A B ) +f (A  B )g: 4.2 Denci Egy f : 2V ! Z fggvnyt jnak hvunk, ha -f (S ) = f (V ; S ) 8S  V halmazra -ha A s B diszjunktak, akkor f (A  B )  maxff (A) f (B )g. 31 4.3 Denci Egy h : 2V ! f0 1g fggvny kikeresztezhet, ha h(V ) = = 0 s brmely kt A B  V halmazra, melyekre h(A) = h(B ) = 1, vagy h(A B ) = h(A  B ) = 1 vagy h(A ; B ) = h(B ; A) = 1. 4.4 Lemma Minden j fggvny ferdn szupermodulris Bizonyts. A j fggvny dencija miatt max(f (A ; B

) f (A B )) f (A) max(f (B ; A) f (A  B )) f (A) max(f (B ; A) f (A B )) f (B ) max(f (A ; B ) f (A  B )) f (B ). A ngy egyenltlensgbl azonnal addik, hogy f (A) + f (B )  max(f (A ; B ) + f (B ; A) f (A B ) + f (A  B )). A kvetkez llts a j fggvny dencijbl azonnal kvetkezik: 4.5 llts Ha f j fggvny, akkor brmely kt diszjunkt A B halmazra, az f (A), f (B ) s f (A  B ) rtkek kzl egyik sem nagyobb a msik kettnl. 4.6 llts Legyen f kikeresztezhet fggvny s S  V egy tartalmazsra nzve minimlis halmaz amelyre f (S ) = 1. Ekkor minden S -t metsz S halmazra f (S ) = 0. 0 0 4.7 llts Legyen f ferdn szupermodulris Legyen h(S ) = 1 ha f (S ) = = fmax s h(S ) = 0 klnben. Ekkor a h fggvny kikeresztezhet 4.8 llts Ha f ferdn szupermodulris s x : E ! R + , akkor f (S ) ; ; x((S )) is ferdn szupermodulris. 4.1 Priml-dul algoritmus Az algoritmust elszr f0 1g rtk j fggvnyekre ismertetjk. Legyen teht f : 2V !

f0 1g egy j fggvny amely egy gyenge orkulummal van megadva, amely egy S halmazra megmondja az f (S ) rtket. Nzzk az (1) feladat relaxcijt s annak duljt. A priml: min cexe X e E 2 8S  V : x((S )) f (S ) 8e 2 E : xe 0: A dul: max X h(S)yS S 32 (2) (3) 8e2E X S :e (S ) yS  ce 2 8 S  V yS 0: Az algoritmus kt fzisbl ll. Az els fzisban leket vesznk be a megoldsba, mg a msodik fzis sorn leket hagyunk el 1. fzis: az algoritmus kiindul az F = priml nem megengedett megoldsbl, s az y  0 dul megengedett megoldsbl. Amg ltezik tartalmazsra nzve minimlis srt halmaz (azaz olyan S , hogy f (S ) = 1 s F (S ) = 0), addig az algoritmus a kvetkezt csinlja: az sszes minimlis srt halmaz dul vltozjt ugyanazzal a szmmal megnveli egszen addig, mg valamely l pontoss nem vlik, azaz valamely lre S: e (S) yS = ce. Az ilyen lek kzl egy tetszlegeset hozzvesznk az F halmazhoz. Az 1 fzis akkor fejezdik be, ha mr nem

ltezik minimlis srt halmaz, azaz amikor F a priml egy megengedett megoldsa. A kvetkez lemma mutatja, hogy a minimlis srt halmazok egyszeren megtallhatak: 4.9 Lemma Az F lhalmazra nzve minimlis srt halmazok pontosan az F sszefgg komponensei. Bizonyts. Legyen S egy tartalmazsra nzve minimlis srt halmaz, amely nem sszefgg. Ekkor persze f (S ) = 1 s F (S ) = 0 Nzzk F sszefgg komponenseit. Mivel F (S ) = 0, ezek kzl nhny S egy partcijt adjk Legyenek ezek S1 : : : Sl  l 2 Ekkor minden i-re F (Si ) = 0 Mivel az Si-k mr nem srtek, ezrt minden i-re f (Si) = 0. Ekkor azonban a 4.5 Lemma miatt f (S ) = 0, ami ellentmonds A 2. fzis sorn azokat az e leket elhagyjuk a megoldsbl, melyekre F ; e minden N komponensre f (N ) = 0. 4.10 llts A msodik fzis utn kapott lek a priml egy megengedett megoldst adjk. Bizonyts. Jellje F az 1 fzis utn kapott leket, F pedig a 2 fzis utn kapott leket. A konstrukci miatt F  F A 49

Lemma miattt elegend beltni, hogy F minden N sszefgg komponensre f (N ) = 0. (2bra) Legyen teht N az F egy sszefgg komponense. F  F miatt N benne van F valamely C komponensben. Mivel F a priml megengedett megoldsa, ezrt f (C ) = 0 Legyenek e1 : : : el az N -bl kilp F -beli lek 1  i  l esetn jellje Ni C ; ei-nek az N -t nem tartalmaz komponenst. Mivel az ei leket a msodik fzis sorn elhagytuk, ezrt 8 i-re f (Ni) = 0. Msrszt C = N  N1 : : : Nl , gy a 4.5 Lemma miatt f (N ) = 0 P 0 0 0 0 0 33 2 F F’ C N2 N1 Nk e2 N ek e1 2. bra: 4.11 Ttel A fenti algoritmus minden f : 2V ! f0 1g j fggvny esetn az (1) feladatra 2 faktoros approximcit ad. Bizonyts. Jellje lf azon diszjunkt S halmazok maximlis szmt, ame- lyekre f (S ) = 1. Az algoritmus meghatrozza (2) egy F megengedett megoldst, s (3) egy y megengedett megoldst gy, hogy a priml complementary slackness felttel teljesl. Azt fogjuk beltni, hogy ce  (2 ; l2 ) f

(S )yS : f S e F 0 X X 2 0 Mivel y a dul egy megengedett megoldsa, ezrt ebbl kvetkezik, hogy az algoritmus ltal vett lek s lya legfeljebb 2-szerese a dul optimumnak, amibl a ttel kvetkezik. A priml complementary slackness teljeslse miatt X ce = X X e F 2 0 e F S :e (S ) 2 0 yS = X yS jF (S)j: 0 S V 2 2 Ezrt elegend beltni, hogy X yS jF (S)j  (2 ; 2 ) X f (S)yS : lf 0 S V 2 S V 2 Az egyenltlensget indukcival ltjuk be. Az algoritmus kezdetn az egyenltlensg trivilisan teljesl, hiszen y  0. Nzznk egy tetszleges itercit, vagyis azt lpst mikor a dul vltozk rtkt nveljk s egy let hozzvesznk F -hez. Jellje C az iterci kezdetn tartalmazsra nzve 34 P minimlis srt halmazok rendszert. Az egyenltlensg bal oldalnak a nvekedse C jF (C )j, mg a jobb oldal nvekedse (2 ; l2f ) jCj, ahol 0 (ennyivel nveltk a dul vltozkat). Mivel jCj  lf , ezrt elegend beltni, hogy minden iterciban 0 2C X jF (C )j 

2jCj ; 2: (4) 0 C 2C A (4) egyenltlensg bizonytsa: Jellje C az iterci kezdetn az aktulis lhalmaz azon sszefgg C komponenseit, melyekre f (C ) = 1. Korbban lttuk, hogy ezek pontosan a tartalmazsra nzve minimlis srt halmazok. Jellje I az iterci kezdetn az aktulis lhalmaz azon sszefgg I komponenseit, melyekre F (I ) 6= 0 s f (I ) = 0. Ksztsnk el egy H grfot: H pontjai legyenek a C s I -beli halmazok, az lei pedig az e 2 F (S ) : S 2 C  I lek. Vegyk szre, hogy H erd lltjuk, hogy H -ban I -beli halmaz nem lehet levl. Tegyk fel indirekt, hogy H -ban ltezik egy I 2 I levl. Legyen e a belle kilp egyetlen l, N pedig F -nek az I -t tartalmaz sszefggsgi komponense. Legyen P illetve N ; P az F -bl az e l elhagysval keletkez kt komponens. Szimmetria miatt feltehetjk, hogy I  P P felbomlik az aktulis iterci szefgg komponenseire: P = P1  : : :  Pk . Mivel I 0 0 P P2 P1 N I e F F’ Pk 3. bra: levl, ezrt F -beli

l nem mehet az I s Pi halmazok kztt. Az algoritmus szablya miatt f (Pi) = 0. Mivel f (I ) = 0, ezrt a 45 Lemma miatt f (P ) = = 0. Tudjuk, hogy f (N ) = 0, ezrt a 45 Lemma miatt f (N ; P ) = 0, de ekkor az e let elhagyhattuk volna a megoldsbl.(3 bra) 0 35 Azt kaptuk teht, hogy a H fban minden levl C -beli. A dN = jF (N )j jellst bevezetve: 0 X dN = X dN ; X dN  2(jCj + jIj ; 1) ; 2jIj = 2jCj ; 2: N 2C N N 2C I 2I Ezzel belttuk a 4.11 Ttelt Ha az f fggvny kikeresztezhet vagy ferdn szupermodulris, akkor a fenti algoritmus nem alkalmazhat, ha f csak a gyenge orkulummal van megadva. Pldul az f (S ) = 1 s f (S ) = 0 S 6= S fggvny kikeresztezhet s ferdn szupermodulris is, s annak eldntsre, hogy egy adott lhalmaz megoldsa-e a feladatnak, a gyenge orkulumot exponencilis sokszor kellene meghvni. Ezeknl a fggvnyosztlyoknl feltesszk, hogy van egy ers orkulumunk, amely egy F lhalmaz (x vektor) esetn megmondja az sszes

tartalmazsra nzve minimlis maximlis srt halmazt, azaz azon minimlis S halmazokat, melyekre f (S ) ; jF (S )j = maxT (f (T ) ; jF (T )j). Jellje ezt az orkulumot max-srt(f,F). A tovbbiakban ezeket a halmazokat maximlis srtknek nevezzk. 0 0 Kikeresztezhet fggvny esetn az algoritmus a kvetkezkppen mdosul: az 1. fzisban az algoritmus kiindul az F = priml nem megengedett megoldsbl s az y  0 dul megengedett megoldsbl. Minden iterciban az algoritmus meghvja a max-srt(f,F) orkulumot. A maximlis srt halmazok dul vltozjt megnveli egy nemnegatv szmmal, amg valamelyik l pontoss nem vlik, azaz S: e (S) yS = ce. Egy pontoss vlt let hozzvesznk F -hez Az 1 fzis akkor fejezdik be, ha mr nem ltezik srt halmaz, azaz amikor F a priml egy megengedett megoldsa. A 2. fzis sorn az F -beli leket fordtott sorrendben vizsgljuk meg, mint ahogy az 1. fzis sorn bekerltek a megoldsba Ha egy e lre F ; e tovbbra is megolds, akkor az e

let elhagyjuk F -bl. A 2 fzis befejezdse utn lesz egy F priml megengedett megoldsunk, s egy y dul megengedett megoldsunk gy, hogy a complementary slackness felttel teljesl: 8e 2 F : S: e (S) yS = ce. 4.12 Ttel A fenti algoritmus minden f kikeresztezhet fggvny esetn az (1) feladatra 2 faktoros approximcit ad. Bizonyts. A 411 Ttel bizonytshoz hasonlan elegend beltni, hogy minden iterciban jF (C )j  2jCj ; 1 P P 2 2 X C 0 2C 36 ahol C az iterci kezdetn maximlis srt halmazok rendszere. Legyen Y = C F (C ). Vilgos, hogy az algoritmus az Y -beli leket az aktulis iterci sorn vagy utna vette be a megoldsba. 4.13 Lemma Minden e 2 Y lhez ltezik egy Se  V halmaz, hogy 1. f (Se) = 1, 2. F (Se) = feg, 3. 8C 2 C halmazra C  Se vagy C Se = Bizonyts. Az, hogy az e let a msodik fzis sorn nem dobtuk ki, pontosan azt jelenti, hogy ltezik egy Se halmaz, hogy f (Se) = 1 s F (Se) = feg Mivel a msodik fzisban az leket fordtva

nzzk vgig, ezrt Se az iterci kezdetn srt volt. Ezrt a 46 llts miatt a 3 tulajdonsg is igaz 0 2C 0 0 Minden e 2 Y lhez vegynk egy fenti tulajdonsg Se halmazt. Jellje S az gy kapott halmazrendszert. Tegyk fel, hogy S -ben lteznek Se s Se metsz halmazok. Mivel f kikeresztezhet, ezrt vagy f (Se  Se ) = f (Se Se ) = 1 vagy f (Se ; Se ) = = f (Se ; Se) = 1. Nzzk az els esetet: cserljk ki az Se Se halmazokat az Se Se s az Se  Se halmazokra. lltjuk, hogy a kt j halmaz tovbbra 0 0 0 0 0 0 0 0 is tanu lesz az e s e lre nzve. A  fggvny szubmodularitst felhasznlva 0 2 = jF (Se)j + jF (Se )j jF (Se Se )j + jF (Se  Se )j 1 + 1: 0 0 0 0 0 0 0 A msodik egyenltlensgnl azt hasznltuk, hogy F megengedett megolds. Teht jF (Se Se )j = jF (Se  Se )j = 1. Kvetkezskppen az Se Se s Se  Se halmazok kzl az egyik az e lre tanu, a msik pedig az e lre. Ha f (Se ; Se ) = f (Se ; Se) = 1, akkor az Se illetve Se halmazokat

cserljk ki az Se ; Se s Se ; Se halmazokra. Az elz esethez hasonlan belthat, hogy tovbbra is egy tan rendszernk lesz. 0 0 0 0 0 0 0 0 0 0 0 0 0 A fenti eljrst folytatva lesz egy 4.13 tulajdonsg S laminris halmazrendszernk (az eljrs vget r mert a metsz prok szma mindig cskken) Vegyk hozz V -t S -hez, s ezen a laminris rendszeren deniljunk egy H ft. Jellje vS az S halmaznak megfelel H -beli pontot (vS  vT ) 2 E (H ) pontosan akkor ha T az S -t tartalmaz legszkebb S -beli halmaz. Minden C 2 C halmazhoz rendeljk hozz az t tartalmaz legszkebb S -beli halmazt. A H fa egy vS pontjt aktvnak hvjuk, ha S hozz van rendelve valamely C 2 C halmazhoz. 37 4.14 Lemma A H fban minden levl (a V -t esetleg kivve) aktv Bizonyts. Egyedl V s a tartalmazsra nzve minimlis S -beli halmazok lehetnek levelek. Brmely tartalmazsra nzve minimlis S -beli halmaz az iterci kezdetn srt, ezrt tartalmaz C -beli halmazt, vagyis ezek a pontok

aktvak. Jellje Ha az aktv H -beli pontok halmazt. 4.15 Lemma C jF (C )j  v Ha dH (v) Bizonyts. Minden e 2 Y lnek egyrtelmen megfeleltetnk egy H -beli let, melynek az egyik vgpontja aktv. Legyen az e 2 F (C ) lhez tartoz S -beli tanuhalmaz Se. Ekkor H -ban ltezik egy (vSe  vT ) l, ahol T az Se-t tartalmaz legszkebb S -beli halmaz. Feleltessk meg az e lnek ezt az let Knnyen lthat, hogy C vagy az Se vagy a T halmazhoz van hozzrendelve, azaz a (vSe  vT ) l egyik vgpontja aktv. P 2C P 0 2 0 4.16 Ttel Minden iterciban fennll a (4) egyenltlensg Bizonyts. Mivel a H fban esetleg a V -t kivve minden levl aktv, ezrt: X dH (v) = X dH (v) ; X dH (v)  2(jH j ; 1) ; 2(jH j ; jHaj) + 1 = v Ha 2 v H v H Ha 2 2jHaj ; 1. Mivel jHaj  jCj s 2 PC 2C ; jF (C )j  Pv Ha dH (v ) X jF (C )j  2jCj ; 1: 0 2 gy 0 C 2C Ezzel belttuk az 4.12 Ttelt A legltalnosabb esetben az f fggvny ferdn szupermodulris. Ekkor az algoritmus fmax

fzisbl ll. Az algoritmus minden fzisban j leket vesz hozz a megoldshoz gy, hogy a maximlis hinyt eggyel cskkenti, gy fmax fzis utn az (1) feladat egy megengedett megoldst kapjuk. Pontosabban: legyen a p: fzis eltt vett lek halmaza Fp 1. Kezdetben F0 = . A p: fzisban az algoritmus meghvja a max-srt(f Fp 1) ers orkulumot. Jellje S az orkulum ltal visszaadott halmazokat (azaz a tartalmazsra nzve minimlis maximlis srt halmazokat). Legyen hp(S ) = = 1 ha S 2 S , klnben h(S ) = 0. A 47 s 48 lltsok szerint a hp fggvny ; ; 38 kikeresztezhet. Az elz rszben ismertetett algoritmussal megoldjuk az albbi IP feladatot: cexe min X e E Fp 1 2 ; ; 8S  V : x(G Fp 1 (S )) hp 1(S ) 8e 2 E ; Fp 1 : xe 2 f0 1g: ; ; ; ; Az algoritmus ltal meghatrozott leket hozzvesszk Fp 1-hez. Indukcival lthat, hogy a p: fzisban azon halmazok hinyt cskkentjk eggyel, melyeknek a p ; 1-dik fzis utn a hinya fmax ; p + 1: 4.17 Ttel A fenti

algoritmus ferdn szupermodulris fggvnyek esetn az (1) feladatra 2 (fmax) approximcit ad, ahol (i) = 1 + 1=2 + : : : 1=i. Bizonyts. Nzzk az (1) feladat albbi LP relaxcijt: ; min X cexe LP e E 2 8S  V : x((S )) f (S ) 8e 2 E : 0  xe  1: A relaxlt feladat dulja: max X h(S)yS ; X ze S 8e 2 E : X S :e (S ) (D) e E 2 yS  ce + ze 2 P 8S  V : yS 0 8e 2 E : ze 0: Legyen y a p: fzisban kapott dul vltoz. Deniljuk ze-t a kvetkezkppen: 8e 2 Fp 1 : ze = S: e (S) yS s ze = 0 egybknt A denci miatt e E ze = e Fp 1 S : e (S ) yS = S jFp 1 (S )jyS : P P P ; 2 2 ; 2 2 P ; 4.18 Lemma Az (y z) vektor a (D) egy megengedett megoldsa Bizonyts. Az y vltozt a (4) feladat megoldsa sorn kaptuk, ezrt P 8 e 2 E ; Fp 1 lre S: e (S) yS = ce. Az e 2 Fp 1 lekre a denci ; ; miatt a (D) feladatbeli egyenltlensg trivilisan teljesl. 2 39 Legyen ZD a (D) optimuma. A 418 Lemma miatt a p: fzisban ZD X f (S)yS ; X ze = X(f (S) ;

jF S e E S 2 j p 1 (S ) )yS ; = (fmax ; p + 1) X yS S ahol felhasznltuk, hogy a p: fzisban csak azoknak a halmazoknak pozitv az y vltozja, melyekre f (S ) ; jFp 1 (S )j = fmax ; p + 1. Felhasznlva, hogy kikeresztezhet fggvnyekre az algoritmus 2-szeres approximcit ad, kapjuk, hogy ; X e Ffmax ce  2 2 X fmax 1 p=1 fmax ; p + 1 ZD = 2 (fmax)ZD ami igazolja a 4.17 Ttelt Ravi s Williamson 16]-ban megmutatta, hogy a ferdn szupermodulris fggvnyeknl hasznlt algoritmus minimlis s ly k-pontsszefgg rszgrf keressre is alkalmazhat. Az algoritmus k fzisbl ll, s minden fzisban a pontsszefggsget eggyel nveli. Ha a p: fzisig az Fp 1 lhalmazt vettk ki, akkor a p: fzisban egy (1) tpus feladatot kell megoldani: minden p ; ; 1 szm pontra, melyek elhagysa utn (V Fp 1) S1 s S2 komponensre esik szt, a (S1  S2) (E ; Fp 1) halmazbl legalbb egy let hozz kell venni Fp 1-hez, azaz itt is felrhat egy (1) tpus feladat. A kikeresztezhet

fggvnyeknl ltott mdon belthat, hogy egy fzison bell a priml-dul algoritmus 2 approximcit ad, s a 4.17 Ttel bizonytshoz hasonlan belthat, hogy a teljes algoritmus 2 (k) approximcis faktort ad. ; ; ; ; Megjegyzs: Fontos ltni, hogy a fejezetben ismertetett algoritmusok nem hasznlnak semmilyen szubrutint, mg a kvetkez rszben hasznlt algoritmus szubrutinknt hasznlja az ellipszoid mdszert. 4.2 Egy 2 faktor approximci Ebben a fejezetben Kamal Jain algoritmust ismertetjk az (1) feladatra ferdn szupermodulris fggvnyek esetn. A feladat relaxcija: min X cexe e E 2 8S  V : x(G(S )) f (S ) 8e 2 E : 0  xe  1: 40 (5) A tovbbiakban feltesszk, hogy az (5) feladatra ltezik egy szeparcis orkulumunk, amely egy x vektorrl megmondja, hogy megengedett megolds, vagy pedig tall egy felttelt melyet x megsrt. Vegyk szre, hogy az ltalnostott Steiner feladat esetn ilyen orkulum ltezik: egy x vektor pontosan akkor elgti ki a

feladatot, ha minden i j prra az i-t s j -t elvlaszt minimlis vgs nagyobb mint rij . Teht az ltalnostott Steiner feladat az ltalunk trgyalt feladat egy specilis esete. Az algoritmus a kvetkez itercit csinlja: 1. lps: oldjuk meg az (5) feladatot 2. lps: (5) egy optimlis megoldsbl csinljunk egy optimlis bzismegoldst 3. lps: azokat az leket, melyeknek a bzismegoldsbeli rtke legalbb 1=2, tegyk be (1) megoldsba (azaz rtkket rgztsk 1-nek) 4. lps: trljk el az elz lpsben lergztett leket, s oldjuk meg a visszamarad feladatot. Mivel a felttel szerint a feladatra van szeparcis orkulumunk, ezrt (5) egy optimlis trtmegoldst megkaphatjuk az ellipszoid mdszer segtsgvel. 4.19 Ttel Az (5) feladat minden x bzismegoldsban 9e : xe 1=2: A ttelt ksbb bizonytjuk. A ttel miatt az lszm mindig legalbb eggyel cskken, gy az algoritmus legfeljebb lszmnyi lps utn vget r. Mg arra van szksgnk, hogy a 4. lpsben

kapott mdostott feladat hasonl tpus mint (5). Legyen X (5) egy optimlis bzismegoldsa, s jellje E 12 + azon leket, melyekre Xe 1=2. Legyen Gres = G ; E 21 + Az E 12 +beli lek rtkt rgztsk egynek, azaz ezeket belevesszk a megoldsba A mdostott feladat: min cexe (6)   X X e E (Gres ) 2 8S  V : x(Gres (S )) f (S ) ; e E 1 + G(S) 2 8e 2 E (Gres) : 0  xe  1: 2 1 A (6) feladatbeli halmazfggvny a 4.8 llts miatt szintn ferdn szupermodulris, ezrt egy (5)-tel megegyez tpus feladatot kaptunk, ezrt ismt alkalmazhatjuk a fenti lpseket. Legfeljebb lszmnyi iterci utn kapunk (2)-nek egy egsz megengedett megoldst. A kvetkez ttel miatt a kapott megolds legfeljebb 2-szerese az optimumnak, amibl kvetkezik, hogy az algoritmus egy 2 approximci. 41 4.20 Ttel Legyen z illetve zres az (5) illetve (6) LP feladatok optimlis   rtke. Ha Eres a (6) feladat olyan egsz megoldsa, melynek a clfggvny rtke legfeljebb 2zres, akkor Eres

 E 21 + (5) egy egsz megoldsa, melynek a clfggvny rtke legfeljebb 2z . Bizonyts. Vilgos, hogy Eres  E 12 + (5) egy megengedett egsz megoldsa Mivel X megszortsa Gres-re megengedett megoldsa a (6) feladatnak, ezrt   X X ce  zres  z ;    e e E1+ 2 2 azaz 2z  X X ce: 2zres +   e E1+ 2 2 Felhasznlva, hogy 8e 2 E 12 + : 2Xe 1 s  2z  X ce + e Eres 2 Az 4.19 Ttel bizonytsa: e X ce  2z , kapjuk, hogy res e Eres X ce:  2 e E1+ 2 2 Legyen X egy megengedett bzismegolds. Ha valamely e lre Xe = 1, akkor kszen vagyunk. Ha valamely e lre Xe = 0, akkor az e let kihagyhatnnk a grfbl. Feltehet teht hogy 0 < Xe < 1 8e 2 E Minden S 2 V halmazra jellje AG(S ) az S halmaznak az LP feladatban megfelel sorvektort. Az A halmazt pontosnak nevezzk, ha X ((A)) = = f (A). 4.21 Lemma Ha A s B pontos halmazok akkor a kvetkez lltsok kzl legalbb az egyik igaz: 1. A ; B s B ; A is pontos, s AG(A) + AG(B ) = AG(A ; B ) +

AG(B ; A) 2. A  B s A B is pontos, s AG(A) + AG(B ) = AG(A  B ) + AG(A B ) Bizonyts. Mivel f ferdn szupermodulris, ezrt vagy f (A) + f (B )   f (A ; B ) + f (B ; A) vagy f (A) + f (B )  f (A  B ) + f (A B ). Tegyk fel, hogy az els teljesl (a msik esetben a bizonyts hasonlan megy). Ekkor egyszer szmolssal addik, hogy X ((A ; B V ; (A  B ))) + X ((B ; A V ; (A  B ))) + 2X ((A  B V ; ; ((A  B ))) + 2X ((A ; B B ; A)) + X ((A ; B A B )) + X ((B ; ; A A B )) = f (A) + f (B )  f (A ; B ) + f (B ; A)  X ((A ; B V ; ; (A  B ))) + X ((B ; A V ; (A  B ))) + 2X ((A  B V ; ((A  B ))) + + X ((A ; B A B )) + X ((B ; A A B )). 42 Az egyenltlensgbl kvetkezik, hogy egyrszt A  B s A B is pontos, msrszt X ((A ; B B ; A)) = 0 ami az lek pozitivitsa miatt azt jelenti hogy az A ; B s a B ; A halmazok kztt nem megy l, amibl kvetkezik, hogy AG(A) + AG(B ) = AG(A ; B ) + AG(B ; A). A T halmazrendszer lljon a pontos

halmazokbl. Tetszleges pontos halmazokbl ll F halmazrendszerre jellje hFi az AG(S ) : S 2 F vektorok ltal kifesztett alteret. 4.22 Lemma Pontos halmazok minden maximlis (azaz nem bvthet) laminris L rendszerre hLi = hT i. Bizonyts. Tegyk fel indirekt hogy ltezik S 2 T pontos halmaz, hogy AG(S ) 62 hLi. Legyen ezen bell S olyan, hogy minimlis szm L-beli halmazt metsz. Legyen L 2 L egy S -t metsz pontos halmaz (ilyen ltezik mert L pontos halmazok maximlis laminris rendszere). A 421 Lemma miatt a kvetkez kt llts kzl legalbb az egyik igaz: 1. S ; L s L ; S is pontosak, s AG(S ) = AG(S ; L) + AG(L ; S ) ;AG (L) 2. S  L s S L is pontosak, s AG(S ) = AG(S  L) + AG(S L) ; AG(L) Tegyk fel, hogy az els teljesl (a bizonyts hasonl a msodik teljeslse esetn is). Mivel AG(S ) 62 hLi, ezrt vagy AG(S ; L) 62 hLi vagy AG(L ; ; S ) 62 hLi. Nzzk az els esetet (a msik eset lnyegben megegyezik) L laminaritsbl knnyen ltszik, hogy minden S ; L-t

metsz L-beli halmaz metszi S -t is. Ekkor azonban S ; L egy olyan pontos halmaz lenne, melyre AG(S ; L) 62 hLi s az S ; L halmazt kevesebb L-beli halmaz metszi mint S -t, ami ellentmond annak, hogy S -t minimlis szm halmaz metsz. A lemma alapjn hT i bzist vehetjk laminris halmazokbl is. A bzismegolds tulajdonsga miatt hT i dimezija jE (G)j-vel egyenl A kvetkez lltst kaptuk: 4.23 Lemma Ltezik B pontos halmazokbl ll laminris halmazrendszer az albbi tulajdonsgokkal: 1. jBj jE (G)j 2. Az AG(S ) : S 2 B vektorok linerisan fggetlenek 3. 8S 2 B f (S ) 1 Az 4.19 Ttel lltsval ellenttben tegyk fel, hogy minden l 1=2-nl kisebb rtket vesz fel. Ebben az esetben belthatjuk az albbi, nmagnak ellentmond lemmt: 4.24 Lemma Ha a bzismegoldsban minden l legfeljebb 1=2-t vesz fel, akkor ltezik pontos halmaz, amelybl legfeljebb kt l megy ki. 43 Bizonyts. Vegyk az 423 Lemmban szerepl B halmazrendszert Egy S  V halmazt rossznak neveznk, ha 0 <

jfA 2 B : A  S gj  je 2 E (G) : e 2 S  S j: Ha ltezik S rossz halmaz akkor B-t s E (G) mdostsuk az albbi mdon: 1. B  B ; fA 2 B : A  S g 2. E (G)  E ; fe 2 E (G) : e 2 S  S g A mdosts utn B sszes 4.23 Lemmban szerepl tulajdonsga meg- marad, ezrt feltehet, hogy rossz halmaz nem ltezik. A szoksos mdon ksztsnk egy T gykeres ft a B  V laminris rendszeren. A T fnak E (G) le van. Ha V a fa egyetlen nem levl pontja, akkor a B-beli halmazok diszjunktak, s ekkor a ttel nyilvnvalan igaz Feltehetjk teht hogy nem V az egyetlen nem levl pontja T -nek. 4.25 llts A T fa pontjaira r tudunk rni nemnegatv egsz szmokat gy, hogy 1. A pontokra rt szmok sszege legfeljebb ktszerese a fa lszmnak 2. Minden pontra, melynek egy gyereke van 2 van rva 3. Minden levlre 2 vagy 4 van rva, s ha azokat a leveleket melyekre 2 van rva elhagyjuk, nem keletkezik j levl. Bizonyts. Legyen W egy mg szmozatlan levl, s U a W szomszdja 4 esetet

klnbztetnk meg attl fggen, hogy U -nak 1 2 3vagy tbb gyereke van. 1.eset: W az U egyetlen gyereke Ekkor persze U 6= V , klnben V lenne az egyetlen nem levl. Mivel nincs rossz halmaz, ezrt nem ltezhet olyan l G-ben, melynek egyik vgpontja W -ben, a msik pedig U -ban van. Msrszt kell lteznie legalbb egy olyan lnek, amely az U halmazbl kilp, de a W -bl nem, mert ellenkez esetben AG(W ) = AG(U ) teljeslne, ami ellentmondana a lineris fggetlensgnek. Mivel az f halmazfggvny egsz, ezrt az olyan lek sszege, melyek U -bl kilpnek de W -bl nem, legalbb 1, ezrt legalbb 3 ilyen l van. Mivel W levl, ezrt W -bl is legalbb 3 l megy ki. Teht itt legalbb 6 lnk van, gy W -re rhatunk 4-t, U -ra pedig 2-t. A tovbbi 3 esetet hasonlan lehet megcsinlni, a bizonytst az olvasra bzzuk. Ha adott a T fa lein egy fenti tulajdonsg szmozs, akkor azon leveleket elhagyva, melyekre 2 van rva, egy olyan ft s pontjain olyan szmozst kapunk, hogy 44

1. A pontokra rt szmok sszege legfeljebb a fa lszma 2. Minden levlre 4 van rva 3. Minden pontra, melynek egy gyereke van, 2 van rva Jellje k0 a levelek szmt, k1 az egy gyerek pontok szmt, k2 pedig a legalbb kt gyerek pontok szmt. A fenti szmozs miatt 2(k0 + k1 + + k2) 2jE (T )j 4k0 + 2k1, azaz k0 < k2. Ez azonban ellentmond a kvetkez lemmnak 4.26 Lemma Tetszleges gykeres T fban k0 > k2 Bizonyts. Mivel az lek szma kisebb mint a pontok szma, ezrt k0 + + k1 + k2 > jE (T )j k1 + 2k2. Ezzel sikerlt beltni a 4.19 Ttelt Ksznetnyilvn ts Szeretnk ksznetet mondani Frank Andrsnak, tmavezetmnek, a dolgozat rsa sorn ny jtott segtsgrt s hasznos tancsairt. Ksznetet mondok tovbb Jttner Alprnak a LATEX -ben ny jtott segtsgrt. 45 sszefoglal tblzat problma komplexits MP NP-teljes SMP ME SME EMP EME GYE GYP SF legjobb approximci hivatkozs 1:5 k = 2 esetn 4] 1 + 1=k k > 2 -re 5] NP-teljes 2 (k) 16] NP-teljes

17=12 k = 2-re 10] 1 + 2=(k + 1) k 3 esetn 5] NP-teljes 2 3] NP-teljes 1:61 k = 1-re 13] 1 + 1=k k 2 esetn 5] NP-teljes 1:61 k = 1-re 13] 2 2p  k  16 esetn 1 + 4= k k 17 esetn 5] megoldhat 1 20] megoldhat 1 9] NP-teljes 2 17] A problmk kdjai: MP: irnytatlan grf minimlis elemszm k-pontsszefgg rszgrfjnak keresse SMP: az MP problma s lyozott esetben ME: irnytatlan grf minimlis elemszm k-lsszefgg rszgrfjnak keresse SME: az ME problma s lyozott esetben EMP: irnytott grf minimlis elemszm k-pontsszefgg rszgrfjnak keresse EME: irnytott grf minimlis elemszm k-lsszefgg rszgrfjnak keresse GYE: irnytott grf minimlis s ly gykeres k-lsszefgg rszgrfjnak keresse GYP: irnytott grf minimlis s ly gykeres k-pontsszefgg rszgrfjnak keresse ST: ltalnostott Steiner feladat Irodalom 1] D. S Hochbaum Approximation algorithms for NP-hard problems PWS Publishing Company, London. 46 2] J. Cheriyan, R

Thurimella Algorithms for paralell k-vertex connectivity and sparse certicates Proc 23rd Annual Symposium on Theory of Computing, 391-401, 1991. 3] S. Khuller and U Vishkin Biconnectivity approximations and graph carvings. Journal of the ACM, 41(2):214-235, 1994 4] N. Garg, V Santosh and Singla Improved approximation algorithms for biconnected subgraphs via better lower bounding techniques. Proc 4th Annual ACM-SIAM Symposium on Discrete Algorithms, 103-111 1993. 5] J. Cheriyan and R Thurimella Approximating Minimum-Size kConnected Spanning Subgraphs via Mathcing 37th Annual Symposium on Foundations of Computer Science, 292-301, 1996 6] W. Mader Ecken vom Grad n in minimalen n-fach zusammenhangenden Graphen. Archive der Mathematik 23 (1972), 219-224 7] S. Khuller and B Raghavachari Improved Approximation Algorithms for Uniform Connectivity Problems. Journal of Algorithms 21, 434-450 (1996) 8] M.Penn and H Shasha-Krupnik Improved Approximation Algorithms for Weighted 2- and

3-Vertex Connectivity Augmentation Problems. Journal of Algorithms 22, 187-196 (1997) 9] A. Frank, Tardos An application of submodular #ows Linear Algebra and its Applications, 114/115:320-348, 1989 10] A. Seb, J Cheriyan, Z Szigeti An improved approximation algorithm for minimum size 2-edge connected spanning subgraphs, 1997 11] A. Frank A survey on T-joins, T-cuts, and conservative weightings Combinatorics, Paul Erds is Eighty (Volume 2) (M. Mikls, V T Ss, T. SZnyi, eds) 12] S. Khuller, B Raghavachari, N Young Approximating the minimum equivalent digraph. SIAM Journal on Computing, 24(4):859-872, 1995 13] S. Khuller, B Raghavachari, N Young On strongly connected digraphs with bounded cycle length. Discrete Applied Mathematics 69 (1996) 281289 47 14] M. XGoemans, DPWilliamson A general approximation technique for constrained forest problems. Proc 3rd Annual ACM-SIAM Symp on Discrete Algorithms, 307-316, 1992. 15] M. Goemans, A Goldberg, S Plotkin, D Shmoys, Tardos, D

Williamson. Improved approximation algorithms for network design problems. Proceedings of the 5th SODA, 307-316, 1992 16] R. Ravi, D Williamson An approximation algorithm for minimum-cost vetex-connectivity problems. Proc 6th Annual ACM-SIAM Symposium on Discrete Algorithms, 332-341, 1995 17] K. Jain A factor 2 approximation algorithm for the generalized Steiner network problem. 18] S. Khuller, R Thurimella Approximation algoritms for graph augmentation Journal of algorithms 14, 214-225 (1993) 19] Z. Nutov, M Penn Faster algorithms for weighted triconnectivity augmentation problems Az ORL-ben fog megjelenni 20] J. Edmonds Matroid intersection Annals of Discrete Mathematics, 4:185-204, 1979. 21] W. Mader Minimalen n-fach zusammenh%ngenden Graphen Archive der Mathematik 23 (1972), 219-224 22] D. P Williamson, M X Goemans, M Mihail, V V Vazirani A primaldual approximation for generalized Steiner network problems Proc of the 25th Annual ACM Symposium on Theory of Computing 708-717,

1993 23] T. Nishizike, S Poljak Highly connected factors with small number of edges. Discrete Applied Mathematics, 55(3):295-297, 1994 24] H. N Gabow, R E Tarjan Faster scaling algorithms for general graph mathcing problems. Journal of the ACM 38 (1991), 815-853 48