Merev körű kiegészítés

A matematika, azon belül a gráfelmélet területén egy irányítatlan G gráf merev körű kiegészítése vagy húrgráffá kiegészítése (chordal completion) a G-vel megegyező csúcshalmazú merev körű gráf, ami a G-t részgráfként tartalmazza. A minimális merev körű kiegészítés (minimal chordal completion) olyan merev körű kiegészítés, mely bármely élének eltávolítása után már nem lenne merev körű kiegészítés. A minimális élszámú merev körű kiegészítés (minimum chordal completion) az összes merev körű kiegészités közül olyan, ami a lehető legkevesebb éllel rendelkezik.

Egy más jellegű merev körű kiegészítés az eredményül kapott húrgráf maximális elemszámú klikkjét minimalizálja, ami alkalmas a G favastagságának meghatározására. A merev körű kiegészítések számos más gráfosztály karakterizálására is alkalmas, ilyenek például a csillagszerű hármas-mentes (AT-free) gráfok, karommentes és csillagszerű hármas-mentes gráfok, valamint a kográfok.

A minimális élszámú merev körű kiegészítés az 1979-ben megjelent Computers and Intractability c. könyvben megjelent tizenkét azon probléma egyike, melyek komplexitása még ismeretlen. A merev körű kiegészítések alkalmazásai közé tartozik a feltöltődés minimalizálása a ritka szimmetrikus mátrixok Gauss-eliminációja során vagy a leszármazási fák rekonstrukciója.

A gráfok húrgráffá kiegészítését néha háromszögelésnek is nevezik,^[1] de ez a megnevezés még a gráfelméleten belül is kétértelmű, hiszen a maximális síkgráfokra is utalhat.

Kapcsolódó gráfcsaládok

Egy G gráf pontosan akkor csillagszerű hármas-mentes, ha minden minimális húrgráffá kiegészítése intervallumgráf. G pontosan akkor karommentes és csillagszerű hármas-mentes gráf, ha minden minimális húrgráffá kiegészítése valódi intervallumgráf. Továbbá G akkor és csak akkor kográf, ha minden minimális húrgráffá kiegészítése triviálisan perfekt gráf.^[1]

Egy G gráf favastagsága pontosan akkor nem haladja meg k-t, ha G rendelkezik legalább egy olyan merev körű kiegészítéssel, melynek maximális elemszámú klikkjének mérete nem nagyobb k + 1-nél. Útszélessége pontosan akkor nem haladja meg k-t, ha G rendelkezik legalább egy olyan merev körű kiegészítéssel, ami intervallumgráf, k + 1-nél nem nagyobb maximális elemszámú klikkel. Sávszélessége pontosan akkor nem haladja meg k-t, ha G rendelkezik legalább egy olyan merev körű kiegészítéssel, ami valódi intervallumgráf, k + 1-nél nem nagyobb maximális elemszámú klikkel.^[2] Mélysége pedig pontosan akkor nem haladja meg k-t, ha G rendelkezik legalább egy olyan merev körű kiegészítéssel, ami triviálisan perfekt gráf, k-nál nem nagyobb maximális elemszámú klikkel.^[3]

Alkalmazásai

A húrgráffá kiegészítés eredeti alkalmazása a ritka szimmetrikus mátrixok Gauss-eliminációja során jelentkező feltöltődés minimalizálása volt. A Gauss-elimináció során a mátrix korábban nulla értékű együtthatóinak egy része nemnulla értéket vesz fel, ami nemkívánatos folyamat, hiszen a további számoláskor lassítja az algoritmus végrehajtását. Egy ritka szimmetrikus mátrixban ezeknek a nemnulla értékeknek a mintázata leírható egy irányítatlan gráffal, melynek a mátrix a szomszédsági mátrixa; a feltöltődő mátrixban a nemnulla értékek mintázata mindig merev körű gráf, valamely minimális merev körű kiegészítés pedig egy ilyen feltöltődési mintázatnak felel meg. Ha adott egy gráf merev körű kiegészítése, megadható az a lépések sorozata, ami a Gauss-elimináció segítségével előállítja ezt a feltöltődési mintázatot az eredményül kapott merev körű gráf eliminációs rendezésével. Ily módon a minimális feltöltődés problémája ekvivalens a minimális élszámú merev körű kiegészítés problémájával.^[4] Ebben az alkalmazásban síkgráfok léphetnek fel kétdimenziós végeselemes rendszerek megoldásaként; a síkgráf-elválasztási tételből adódóan egy n csúcsú síkgráfnak mindig létezik legfeljebb O(n log n) élből álló merev körű kiegészítése.^[5]

Másik fő alkalmazási terület a leszármazási fák területe, az evolúciós fák rekonstruálása, legyenek azok a filogenetikus rendszertanban a genetikai mutációknak kitett élőlények leszármazási fái, vagy akár ókori kéziratok manuális másolása során fellépő hibák által meghatározott leszármazási fák. Ha fel lehet tételezni, hogy minden mutáció vagy másolási hiba csak egyetlenegyszer fordul elő, tökéletes leszármazási fa nyerhető, melyben a valamely speciális tulajdonsággal rendelkező fajok vagy kéziratok mindig egy összefüggő részfát alkotnak. (Buneman 1974) megállapítása szerint a tökéletes leszármazási fa merev körű kiegészítési problémaként modellezhető. Megadunk egy G „átfedési gráfot” (overlap graph), melynek csúcsai az attribútumértékek (a faj vagy kézirat valamely karakterisztikus értéke), az élek pedig olyan attribútumpárokat jelképeznek, melyek legalább még egy fajban jelen vannak. A gráf csúcsai színezhető az egyes attribútumok karakterisztikájának azonosságai szerint, így a színek száma megegyezik a leszármazási fában szereplő karakterisztikák számával. A tökéletes leszármazási fa pontosan akkor létezik, ha G rendelkezik a színezést tiszteletben tartó merev körű kiegészítéssel.^[6]

Számítási bonyolultság

Bár az 1979-es Computers and Intractability megoldatlanként kezeli,^[7] a minimális élszámú merev körű kiegészítés problémája (avagy a minimális feltöltődés (minimum fill-in) probléma) bonyolultsága gyorsan eldőlt: (Yannakakis 1981) igazolta, hogy NP-teljes.^[8] Ha a minimális élszámú merev körű kiegészítés k éllel bővíti a G gráfot, akkor polinom idejű algoritmussal lehetséges találni legfeljebb 8k² élt felhasználó merev körű kiegészítést.^[9] Az optimális hozzáadandó k élhalmaz megkeresése rögzített paraméter mellett kezelhető, a gráf méretét tekintve polinom időben, k-ban pedig szubexponenciálisan.^[10]

A favastagság (a merev körű kiegészítés minimális klikkmérete) és a kapcsolódó paraméterek, mint az útszélesség és a fa mélysége szintén NP-teljesek, és (hacsaknem P=NP) optimális értékük nem közelíthető polinom időben konstans faktorral; léteznek azonban logaritmikus közelítési arányt elérő approximációs algoritmusok hozzájuk.^[11]

Mind a minimális feltöltés, mind a favastagság problémája exponenciális időben megoldhatók. Precízebben, egy n-csúcsú gráfban a szükséges idő O(1,9601ⁿ).^[12]

Fordítás

• Ez a szócikk részben vagy egészben a Chordal completion című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

1. Parra, Andreas & Scheffler, Petra (1997), "Characterizations and algorithmic applications of chordal graph embeddings", Discrete Applied Mathematics 79 (1-3): 171–188, DOI 10.1016/S0166-218X(97)00041-3.
2. Kaplan, Haim & Shamir, Ron (1996), "Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques", SIAM Journal on Computing 25 (3): 540–561, DOI 10.1137/S0097539793258143.
3. Eppstein, David (November 15, 2012), Graph parameters and cliques in supergraphs, <http://11011110.livejournal.com/258705.html>. Hozzáférés ideje: 2017-03-29 Archiválva 2014. január 9-i dátummal a Wayback Machine-ben Archivált másolat. [2014. január 9-i dátummal az eredetiből archiválva]. (Hozzáférés: 2017. március 29.).
4. Rose, Donald J. (1972), "A graph-theoretic study of the numerical solution of sparse positive definite systems of linear equations", Graph theory and computing, Academic Press, New York, pp. 183–217.
5. Chung, F. R. K. & Mumford, David (1994), "Chordal completions of planar graphs", Journal of Combinatorial Theory, Series B 62 (1): 96–106, DOI 10.1006/jctb.1994.1056.
6. Buneman, Peter (1974), "A characterisation of rigid circuit graphs", Discrete Mathematics 9: 205–212, DOI 10.1016/0012-365X(74)90002-8.
7. Garey, Michael R.; Johnson, David S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman, ISBN 0-7167-1045-5, [OPEN4], p. 286; update, p. 339.
8. Yannakakis, Mihalis (1981), "Computing the minimum fill-in is NP-complete", Society for Industrial and Applied Mathematics 2 (1): 77–79, DOI 10.1137/0602010.
9. Natanzon, Assaf; Shamir, Ron & Sharan, Roded (2000), "A polynomial approximation algorithm for the minimum fill-in problem", SIAM Journal on Computing 30 (4): 1067–1079, DOI 10.1137/S0097539798336073.
10. Fomin, Fedor V. & Villanger, Yngve (2013), "Subexponential parameterized algorithm for minimum fill-in", SIAM Journal on Computing 42 (6): 2197–2216, DOI 10.1137/11085390X.
11. Bodlaender, Hans L.; Gilbert, John R. & Hafsteinsson, Hjálmtýr et al. (1995), "Approximating treewidth, pathwidth, frontsize, and shortest elimination tree", Journal of Algorithms 18 (2): 238–255, DOI 10.1006/jagm.1995.1009.
12. Fomin, Fedor V.; Kratsch, Dieter & Todinca, Ioan (2004), "Exact (exponential) algorithms for treewidth and minimum fill-In", Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004, Proceedings, vol. 3142, Lecture Notes in Computer Science, Springer-Verlag, pp. 568–580, DOI 10.1007/978-3-540-27836-8_49.