Metrická dimenze (teorie grafů) - Metric dimension (graph theory)
v teorie grafů, metrická dimenze grafu G je minimální mohutnost podmnožiny S vrcholů tak, že všechny ostatní vrcholy jsou jednoznačně určeny jejich vzdálenostmi k vrcholům v S. Nalezení metrické dimenze grafu je NP-tvrdé problém; rozhodovací verze, která určuje, zda je metrická dimenze menší než daná hodnota, je NP-kompletní.
Podrobná definice
Pro objednanou podmnožinu vrcholů a vrcholu proti v připojeném grafu G, zastoupení proti s ohledem na Ž je objednaný k-tuple , kde d(X,y) představuje vzdálenost mezi vrcholy X a y. Sada Ž je rozlišovací sada (nebo vyhledávací sada) pro G pokud každé dva vrcholy G mají odlišné reprezentace. Metrická dimenze G je minimální mohutnost rozlišovací sady pro G. Rozlišovací sada obsahující minimální počet vrcholů se nazývá základ (nebo referenční sada) pro G. Rozlišovací sady pro grafy představil samostatně Slater (1975) a Harary & Melter (1976), zatímco koncept řešení a metrické dimenze byl definován mnohem dříve v obecnějším kontextu metrických prostorů Blumenthal ve své monografii Teorie a aplikace geometrie vzdálenosti. Grafy jsou speciální příklady metrických prostorů s jejich metrikou vnitřní cesty.
Stromy
Slater (1975) (viz také Harary & Melter (1976) a Khuller, Raghavachari & Rosenfeld (1996) ) poskytuje následující jednoduchou charakterizaci metrické dimenze a strom. Pokud je strom cestou, jeho metrická dimenze je jedna. Jinak nechte L označuje množinu vrcholů prvního stupně ve stromu (obvykle se nazývá listy, i když Slater toto slovo používá odlišně). Nechat K. být množina vrcholů, které mají stupeň větší než dva a které jsou spojeny cestami vrcholů druhého stupně s jedním nebo více listy. Pak je metrická dimenze |L| − |K.|. Základ této mohutnosti lze vytvořit odstraněním z L jeden z listů spojených s každým vrcholem v K.. Stejný algoritmus platí pro spojnicový graf stromu, jak dokazuje Feng, Xu & Wang (2013) (a tedy jakýkoli strom a jeho spojnicový graf mají stejnou metrickou dimenzi).
Vlastnosti
v Chartrand a kol. (2000), je prokázáno, že:
- Metrická dimenze grafu G je 1 právě tehdy G je cesta.
- Metrická dimenze n-vertexový graf je n − 1 právě když je to kompletní graf.
- Metrická dimenze n-vertexový graf je n − 2 právě když je graf a kompletní bipartitní graf K.s, t, a dělený graf nebo .
Vztahy mezi řádem, metrickým rozměrem a průměrem
Khuller, Raghavachari & Rosenfeld (1996) prokázat nerovnost pro všechny n-vrcholový graf s průměr D a metrická dimenze β. Tato hranice vyplývá ze skutečnosti, že každý vrchol, který není v rozlišovací sadě, je jednoznačně určen vektorem vzdálenosti o délce β, přičemž každá položka je celé číslo mezi 1 a D (existují přesně takové vektory). Vazby je však dosaženo pouze pro nebo ; přesněji svázaný dokazuje Hernando a kol. (2010).
Pro konkrétní třídy grafů mohou platit menší hranice. Například, Beaudou et al. (2018) dokázal to pro stromy (pevná vazba pro sudé hodnoty D) a vazba formuláře pro vnější rovinné grafy. Stejní autoři to dokázali pro grafy bez č kompletní graf řádu t jako Méně důležitý a také dal hranice pro chordální grafy a grafy ohraničené šířka stromu. Autoři Foucaud a kol. (2017a) prokázané hranice formuláře pro intervalové grafy a permutační grafy a hranice formuláře pro grafy jednotkových intervalů, bipartitní permutační grafy a cographs.
Výpočetní složitost
Složitost rozhodnutí
Rozhodování, zda je metrická dimenze grafu nanejvýš dané celé číslo, je NP-úplné (Garey & Johnson 1979 ). Pro omezený stupeň zůstává NP úplný rovinné grafy (Díaz et al. 2012 ), rozdělené grafy, bipartitní grafy a jejich doplňuje, spojnicové grafy bipartitních grafů (Epstein, Levin & Woeginger 2012 ), jednotkové diskové grafy (Hoffmann & Wanke 2012 ), intervalové grafy o průměru 2 a permutační grafy o průměru 2 (Foucaud a kol. 2017b ).
Pro jakoukoli pevnou konstantu k, maximálně grafy metrické dimenze k lze rozpoznat v polynomiální čas, testováním všeho možného k-tuples vrcholů, ale tento algoritmus není fixovatelný parametr (pro přirozený parametr k, velikost řešení). Odpověď na otázku položenou Lokshtanov (2010), Hartung & Nichterlein (2013) ukazují, že problém s rozhodováním o metrické dimenzi je dokončen pro parametrizovanou třídu složitosti W [2], z čehož vyplývá, že časově omezený tvar nÓ(k) jak je dosaženo tímto naivním algoritmem, je pravděpodobně optimální a že použitelný algoritmus s pevnými parametry (pro parametrizaci k) pravděpodobně nebude existovat. Problém se však stává fixovatelný parametr pokud je omezeno na intervalové grafy (Foucaud a kol. 2017b ) a obecněji ke grafům ohraničené délky stromu (Belmonte a kol. 2015 ), jako chordální grafy, permutační grafy nebo asteroidové trojnásobné grafy.
Rozhodnutí, zda metrická dimenze stromu je nanejvýš dané celé číslo, lze provést v lineárním čase (Slater 1975; Harary & Melter 1976 ). Další algoritmy lineárního času existují pro cographs (Epstein, Levin & Woeginger 2012 ), řetězové grafy (Fernau a kol. 2015 ) a kaktusové blokové grafy (Hoffmann, Elterman & Wanke 2016 ) (třída zahrnující obě kaktusové grafy a blokové grafy ). Problém může být vyřešen v polynomiálním čase vnější rovinné grafy (Díaz et al. 2012 ). To může být také řešeno v polynomiálním čase pro grafy ohraničené cyklomatické číslo (Epstein, Levin & Woeginger 2012 ), ale tento algoritmus opět není fixovatelný s pevným parametrem (pro parametr „cyklomatické číslo“), protože exponent v polynomu závisí na cyklomatickém čísle. K vyřešení problému metrické dimenze pro parametry existují algoritmy umožňující fixaci parametrůvrcholový kryt " (Hartung & Nichterlein 2013 ), „maximální počet listů“ (Eppstein 2015 ) a „modulární šířka“ (Belmonte a kol. 2015 ). Grafy s omezeným cyklomatickým číslem, číslem vrcholového krytu nebo maximálním počtem listů jsou všechny ohraničené šířka stromu, je však otevřeným problémem určit složitost problému metrické dimenze i na grafech o šířce stromu 2, tj. sériově paralelní grafy (Belmonte a kol. 2015 ).
Složitost aproximace
Metrická dimenze libovolné n-vertexový graf lze aproximovat v polynomiálním čase na v rámci přibližný poměr z vyjádřením jako nastavit problém s krytem, problém pokrytí celé dané kolekce prvků co nejméně sadami v daném rodina sad (Khuller, Raghavachari & Rosenfeld 1996 ). V úloze pokrytí sady vytvořené z problému metrické dimenze jsou prvky, které mají být pokryty, páry vrcholů, které mají být rozlišeny, a množiny, které je mohou pokrýt, jsou sady dvojic, které lze odlišit jedním zvoleným vrcholem. Potom následuje aproximační vazba použitím standardních aproximačních algoritmů pro kryt setu. Alternativní chamtivý algoritmus který vybírá vrcholy podle rozdílu v entropie mezi třídami ekvivalence vektorů vzdálenosti před a po výběru se dosáhne ještě lepšího aproximačního poměru, (Hauptmann, Schmied & Viehmann 2012 ). Tento aproximační poměr se blíží nejlepšímu možnému výsledku, protože za standardních teoreticko-teoretických předpokladů je poměr nelze v žádném případě dosáhnout v polynomiálním čase (Hauptmann, Schmied & Viehmann 2012 ). Druhá tvrdost aproximace stále platí pro instance omezené na subkubické grafy (Hartung & Nichterlein 2013 ), a dokonce i bipartitní subkubické grafy, jak ukazuje Hartungova disertační práce (Hartung 2014 ).
Reference
- Beaudou, Laurent; Dankelmann, Peter; Foucaud, Florent; Henning, Michael A .; Mary, Arnaud; Parreau, Aline (2018), „Ohraničení pořadí grafu pomocí jeho průměru a metrické dimenze: studie prostřednictvím rozkladů stromů a dimenze VC“, SIAM Journal on Discrete Mathematics, 32 (2): 902–918, arXiv:1610.01475, doi:10.1137 / 16M1097833, S2CID 51882750
- Belmonte, R .; Fomin, F. V .; Golovach, P. A .; Ramanujan, M. S. (2015), „Metric dimension of bounded width graphs“, in Italiano, G. F .; Pighizzini, G .; Sannella, D. T. (eds.), Mathematical Foundations of Computer Science 2015 - MFCS 2015: 40. mezinárodní sympozium, Milán, Itálie, 24. – 28. Srpna 2015, sborník, Přednášky z informatiky, 9235, Springer, str. 115–126, doi:10.1007/978-3-662-48054-0_10.
- Blumenthal, L.M. (1953), Teorie a aplikace geometrie vzdálenosti, Clarendon, Oxford.
- Buczkowski, P .; Chartrand, G.; Poisson, C .; Zhang, P. (2003), „On k-dimenzionální grafy a jejich základy ", Periodica Mathematica Hungarica, 46 (1): 9–15, doi:10.1023 / A: 1025745406160, PAN 1975342, S2CID 33390310.
- Chartrand, G.; Eroh, L .; Johnson, M. A .; Oellermann, O. R. (2000), „Rozlišitelnost v grafech a metrická dimenze grafu“, Diskrétní aplikovaná matematika, 105 (1–3): 99–113, doi:10.1016 / S0166-218X (00) 00198-0, hdl:10338.dmlcz / 127843, PAN 1780464.
- Díaz, J .; Pottonen, O .; Serna, M. J .; van Leeuwen, E. J. (2012), „O složitosti metrické dimenze“ (PDF)v Epstein, Leah; Ferragina, Paolo (eds.), Algoritmy - ESA 2012: 20. výroční evropské sympozium, Lublaň, Slovinsko, 10. – 12. Září 2012, sborník, Přednášky v informatice, 7501, Springer, str. 419–430, arXiv:1107.2256, doi:10.1007/978-3-642-33090-2_37.
- Eppstein, David (2015), „Metrická dimenze parametrizovaná maximálním počtem listů“, Journal of Graph Algorithms and Applications, 19 (1): 313–323, arXiv:1506.01749, doi:10,7155 / jgaa.00360, S2CID 1318601.
- Epstein, Leah; Levin, Asaf; Woeginger, Gerhard J. (2012), „(vážená) metrická dimenze grafů: těžké a snadné případy“, in Golumbic, Martin Charles; Stern, Michal; Levy, Avivit; et al. (eds.), Graficko-teoretické koncepce v informatice: 38. mezinárodní workshop, WG 2012, Jeruzalém, Izrael, 26. – 28. Června 2012, revidované vybrané příspěvky, Přednášky v informatice, 7551, str. 114–125, doi:10.1007/978-3-642-34611-8_14.
- Feng, Min; Xu, min; Wang, Kaishun (2013), „O metrické dimenzi spojnicových grafů“, Diskrétní aplikovaná matematika, 161 (6): 802–805, arXiv:1107.4140, doi:10.1016 / j.dam.2012.10.018, S2CID 36010185.
- Fernau, Henning; Heggernes, Pinar; van 't Hof, Pim; Meister, Daniel; Saei, Reza (2015), „Výpočet metrické dimenze pro řetězové grafy“, Dopisy o zpracování informací, 115 (9): 671–676, doi:10.1016 / j.ipl.2015.04.006.
- Foucaud, Florent; Mertzios, George B .; Naserasr, Reza; Parreau, Aline; Valicov, Petru (2017a), "Identifikace, dominance polohy a metrická dimenze na intervalových a permutačních grafech. I. Hranice", Teoretická informatika, 68: 43–58, arXiv:1507.08164, doi:10.1016 / j.tcs.2017.01.006, S2CID 25244200
- Foucaud, Florent; Mertzios, George B .; Naserasr, Reza; Parreau, Aline; Valicov, Petru (2017b), "Identifikace, dominance polohy a metrická dimenze na intervalových a permutačních grafech. II. Algoritmy a složitost", Algorithmica, 78 (3): 914–944, arXiv:1405.2424, doi:10.1007 / s00453-016-0184-1, S2CID 1520161.
- Garey, M. R.; Johnson, D. S. (1979), Počítače a neodolatelnost: Průvodce po teorii NP-úplnosti, W.H. Freemane, ISBN 0-7167-1045-5 A1.5: GT61, s. 204.
- Harary, F.; Melter, R. A. (1976), „O metrické dimenzi grafu“, Ars Combinatoria, 2: 191–195, PAN 0457289.
- Hartung, Sepp (2014), Zkoumání mezer parametrů při zvládání výpočetní neřešitelnosti, disertační práce, Technische Universität Berlin, vyvoláno 2015-09-15.
- Hartung, Sepp; Nichterlein, André (2013), „O parametrizované a aproximační tvrdosti metrické dimenze“, Konference IEEE 2013 o výpočetní složitosti (CCC), Stanford, CA, USA, 5. – 7. Června 2013, sborník, IEEE, s. 266–276, arXiv:1211.1636, doi:10.1109 / CCC.2013.36, S2CID 684505.
- Hauptmann, Mathias; Schmied, Richard; Viehmann, Claus (2012), „Aproximační složitost problému metrické dimenze“, Journal of Discrete Algorithms, 14: 214–222, doi:10.1016 / j.jda.2011.12.010, PAN 2922072.
- Hernando, Carmen; Mora, Mercè; Pelayo, Ignacio M .; Seara, Carlos; Wood, David R. (2010), „Extrémní teorie grafů pro metrické rozměry a průměr“, Electronic Journal of Combinatorics, 17: # R30, doi:10.37236/302.
- Hoffmann, Stefan; Elterman, Alina; Wanke, Egon (2016), „Lineární časový algoritmus pro metrickou dimenzi grafů kaktusových bloků“, Teoretická informatika, 630: 43–62, doi:10.1016 / j.tcs.2016.03.024
- Hoffmann, Stefan; Wanke, Egon (2012), „Metric Dimension for Gabriel Unit Disk Graphs Is NP-Complete“, Bar-Noy, Amotz; Halldórsson, Magnús M. (eds.), Algorithms for Sensor Systems: 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2012, Ljubljana, Slovenia, 13-14 September, 2012, Revised Selected Papers, Přednášky v informatice, 7718, Springer, str. 90–92, arXiv:1306.2187, doi:10.1007/978-3-642-36092-3_10, S2CID 9740623.
- Khuller, S.; Raghavachari, B .; Rosenfeld, A. (1996), "Orientační body v grafech", Diskrétní aplikovaná matematika, 70 (3): 217–229, doi:10.1016 / 0166-218x (95) 00106-2, hdl:10338.dmlcz / 140702.
- Lokshtanov, Daniel (2010), „Otevřené problémy - Parametrizovaná složitost a aproximační algoritmy: Metrická dimenze“, v Demaine, Erik D.; Hajiaghayi, MohammadTaghi; Marx, Dániel (eds.), Parametrizovaná složitost a přibližné algoritmy, Sborník seminářů Dagstuhl, Dagstuhl, Německo: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
- Slater, P. J. (1975), „Listy stromů“, Proc. 6. jihovýchodní konference o kombinatorice, teorii grafů a výpočtu (Florida Atlantic Univ., Boca Raton, Florida, 1975), Congressus Numerantium, 14, Winnipeg: Utilitas Math., Str. 549–559, PAN 0422062.
- Slater, P. J. (1988), „Dominující a referenční sady v grafu“, Journal of Mathematical and Physical Sciences, 22 (4): 445–455, PAN 0966610.