K-minimální kostra - K-minimum spanning tree

Příklad neorientovaného grafu s hraničními náklady
4-MST z
6-MST z

The k-minimální problém překlenujícího stromu, studoval v teoretická informatika, požaduje strom s minimálními náklady, který má přesně k vrcholy a tvoří podgraf většího grafu. Také se tomu říká k-MST nebo vážený na hraně k-kardinalita strom. Nalezení tohoto stromu je NP-tvrdé, ale lze jej aproximovat v rámci konstanty přibližný poměr v polynomiální čas.

Problémové prohlášení

Vstup do problému se skládá z neorientovaný graf se závažími na okrajích a číslo k. Výstupem je strom s k vrcholy a k − 1 hrany, přičemž všechny hrany výstupního stromu patří do vstupního grafu. Náklady na výstup jsou součtem vah jeho okrajů a cílem je najít strom, který má minimální náklady. Problém formuloval Lozovanu a Zelikovsky (1993)[1] a tím Ravi a kol. (1996).

Ravi a kol. považována také za geometrickou verzi úlohy, kterou lze považovat za zvláštní případ problému s grafem k-minimální problém překlenovacího stromu, vstup je sada bodů v rovině. Výstup by měl být opět strom s k bodů jako jeho vrcholy, čímž se minimalizuje součet Euklidovská délka jeho okrajů. To znamená, že jde o graf k-minimální kostra na a kompletní graf s euklidovskými vzdálenostmi jako váhami.[2]

Výpočetní složitost

Když k je pevná konstanta, k-minimální problém s překlenovacím stromem lze vyřešit v polynomiální čas podle a vyhledávání hrubou silou algoritmus, který zkouší vše k-tuples of vertices.However, for variable k, k-minimální problém překlenujícího stromu se ukázal být NP-tvrdé podle a snížení z Steinerův strom problém.[1][2]

Redukce bere jako vstup instanci problému Steinerova stromu: vážený graf s podmnožinou jeho vrcholů vybraných jako terminály. Cílem problému Steinerova stromu je spojit tyto terminály se stromem, jehož hmotnost je co nejmenší. Transformovat tento problém na instanci k-minimální problém překlenujícího stromu, Ravi a kol. (1996) připojit ke každému terminálu strom hran s nulovou hmotností s velkým počtem t vrcholů na strom. (Pro graf s n vrcholy a r terminály, které používají t = n − r − 1 přidali vrcholy na strom.) Poté požádají o k-minimální kostra v tomto rozšířeném grafu s k = rt. Jediný způsob, jak zahrnout tolik vrcholů do a k-panning tree je použít alespoň jeden vrchol z každého přidaného stromu, protože nezbývá dostatek vrcholů, pokud by se některý z přidaných stromů minul. Nicméně, pro tuto volbu k, je možné pro k-rozpínací strom tak, aby zahrnoval jen tolik okrajů původního grafu, kolik je potřeba pro připojení všech terminálů. Proto k-minimální překlenující strom musí být vytvořen kombinací optimálního Steinerova stromu s dostatečným množstvím hran nulové hmotnosti přidaných stromů, aby byla celková velikost stromu dostatečně velká.[2]

Dokonce i pro graf, jehož okrajové váhy patří do sady {1, 2, 3}, testování, zda je optimální hodnota řešení menší než daná prahová hodnota NP-kompletní. Zůstává NP kompletní rovinné grafy. Geometrická verze problému je také NP-tvrdá, ale není známo, že patří do NP, kvůli obtížnosti porovnávání součtů odmocnin; místo toho spočívá ve třídě problémů redukovatelných na existenciální teorie skutečností.[2]

The k-minimální kostra se nachází v polynomiální čas pro grafy ohraničené šířka stromu, a pro grafy pouze se dvěma odlišnými vahami hran.[2]

Aproximační algoritmy

Vzhledem k vysoké výpočetní složitosti hledání optimálního řešení k- minimální klenutý strom, většina výzkumu problému se místo toho soustředila na aproximační algoritmy kvůli problému. Cílem těchto algoritmů je najít přibližné řešení v polynomiálním čase s malým přibližný poměr. Aproximační poměr je definován jako poměr délky vypočítaného řešení k optimální délce pro nejhorší případ, který maximalizuje tento poměr. Protože snížení tvrdosti NP pro k-minimální problém překlenovacího stromu zachovává váhu všech řešení, zachovává také tvrdost aproximace problému. Zejména proto, že problém se Steinerovým stromem je NP těžko aproximovatelný na přibližný poměr lepší než 96/95,[3] totéž platí pro k-minimální problém překlenujícího stromu.

Nejlepší aproximace známá pro obecný problém dosahuje aproximačního poměru 2 a je o Garg (2005).[4] Tato aproximace silně závisí na schématu primal-dual Goemans & Williamson (1992).[5]Pokud se vstup skládá z bodů v Euklidovské letadlo (libovolné dva z nich lze ve stromu spojit s cenou rovnou jejich vzdálenosti) existuje a polynomiální časové aproximační schéma vymyslel Arora (1998).[6]

Reference

  1. ^ A b Lozovanu, D .; Zelikovsky, A. (1993), "Minimální a ohraničené problémy stromů", Tezele Congresului XVIII al Academiei Romano-Americane, Kishniev, str. 25. Jak uvádí Ravi a kol. (1996).
  2. ^ A b C d E Ravi, R .; Sundaram, R .; Marathe, M .; Rosenkrantz, D .; Ravi, S. (1996), "Spanning trees short or small", SIAM Journal on Discrete Mathematics, 9 (2): 178–200, arXiv:matematika / 9409222, doi:10.1137 / S0895480194266331, S2CID  8253322. Předběžná verze této práce byla představena dříve, na 5. výročním sympoziu ACM-SIAM o diskrétních algoritmech, 1994, s. 546–555.
  3. ^ Chlebík, Miroslav; Chlebíková, Janka (2008), „Problém Steinerova stromu v grafech: výsledky nepřibližnosti“, Teoretická informatika, 406 (3): 207–214, doi:10.1016 / j.tcs.2008.06.046.
  4. ^ Garg, Naveen (2005), „Uložení epsilon: 2-aproximace problému k-MST v grafech“, Proceedings of the 37.th ACM Symposium on Theory of Computing, str. 396–402, doi:10.1145/1060590.1060650, S2CID  17089806..
  5. ^ Goemans, M.; Williamson, P. (1992), „Obecná aproximační technika pro omezené lesní problémy“, SIAM Journal on Computing, 24 (2): 296–317, CiteSeerX  10.1.1.55.7342, doi:10.1137 / S0097539793242618, S2CID  1796896.
  6. ^ Arora, Sanjeev (1998), „Schémata polynomiálního přibližování času pro euklidovského obchodního cestujícího a další geometrické problémy“, Deník ACM, 45 (5): 753–782, doi:10.1145/290179.290180, S2CID  3023351.

externí odkazy