Metrisk dimension (grafteori)

I grafteorin är den metriska dimensionen av en graf G den minsta kardinaliteten för en delmängd S av hörn så att alla andra hörn bestäms unikt av deras avstånd till hörnen i S. Att hitta den metriska dimensionen av en graf är ett NP-svårt problem; beslutsversionen, som avgör om den metriska dimensionen är mindre än ett givet värde, är NP-komplett .

Detaljerad definition

För en ordnad delmängd $W=\{w_{1},w_{2},\dots ,w_{k}\}$ av hörn och en vertex v i en sammankopplad graf G , representationen av v med avseende på W är den ordnade k -tuppeln $r(v|W)=(d(v,w_{1}),d(v,w_{2}),\dots ,d(v,w_{k}))$ , där d ( x , y ) representerar avståndet mellan hörnen x och y . Mängden W är en upplösningsmängd (eller lokaliseringsmängd) för G om vartannat hörn av G har distinkta representationer. Den metriska dimensionen för G är den lägsta kardinaliteten för en upplösningsmängd för G . En upplösningsmängd som innehåller ett minsta antal hörn kallas en bas (eller referensmängd) för G . Upplösningsuppsättningar för grafer introducerades oberoende av Slater (1975) och Harary & Melter (1976), medan begreppet en upplösningsmängd och den metriska dimensionen definierades mycket tidigare i det mer allmänna sammanhanget med metriska rum av Blumenthal i sin monografi Theory och tillämpningar av avståndsgeometri . Grafer är speciella exempel på metriska utrymmen med deras inneboende banmått.

Träd

Om ett träd är en bana är dess metriska dimension en. I annat fall, låt L beteckna uppsättningen av löv, grad-1 hörn i trädet. Låt K vara uppsättningen av hörn som har en grad som är större än två, och som är sammankopplade med banor av två graders hörn till ett eller flera blad. Då är den metriska dimensionen | L | − | K |. En grund för denna kardinalitet kan bildas genom att ta bort från L ett av bladen som är associerade med varje vertex i K . Samma algoritm är giltig för trädets linjediagram, och därför har alla träd och dess linjediagram samma metriska dimension.

Egenskaper

I Chartrand et al. (2000) , är det bevisat att:

• Den metriska dimensionen för en graf G är 1 om och endast om G är en väg.
• Den metriska dimensionen för en n -vertexgraf är n −1 om och endast om det är en komplett graf .
• Den metriska dimensionen för en n -vertexgraf är n − 2 om och endast om grafen är en komplett tvådelad graf K _{s , t} , en delad graf ${\displaystyle K_{s}+{\överlinje {K_{t}}}(s\geq 1,t\geq 2)} , eller K s$ + $K_ {s}+(K_{1}\kopp K_{t})(s,t\geq 1)}$ .

Relationer mellan ordningen, den metriska dimensionen och diametern

Khuller, Raghavachari & Rosenfeld (1996) bevisar olikheten $n\leq D^{\beta }+\beta$ för varje n -vertexgraf med diameter $D$ och metrisk dimension $\beta$ . Dessa gränser följer av det faktum att varje vertex som inte finns i den upplösande mängden bestäms unikt av en avståndsvektor med längden $\beta$ där varje post är ett heltal mellan 1 och $D$ (det finns just $D^{\beta }$ sådana vektorer). Dock uppnås gränsen endast för $D\leq 3$ eller $\beta =1$ ; desto mer exakt bunden

$$n\leq \left(\lfloor 2D/3\rfloor + 1\right)^{\beta }+\beta \sum _{i=1}^{\lceil D/3\rceil }(2i-1)^{\beta -1}$$

bevisas av Hernando et al. (2010) .

För specifika grafklasser kan mindre gränser gälla. Till exempel, Beaudou et al. (2018) bevisade att $n\leq (\beta D+4)(D+2)/8$ för träd (gränsen är snäv för jämnt värden på D ), och en gräns av formen $n=O(D^{2}\beta )$ för ytterplanära grafer . Samma författare bevisade att $n\leq (D\beta +1)^{t-1}$ för grafer utan fullständig graf av ordningen t som moll och även gav gränser för ackordsgrafer och grafer för avgränsad trädbredd . Författarna Foucaud et al. (2017a) bevisade gränser av formen $n=O(D\beta ^{2})$ för intervallgrafer och permutationsgrafer och gränser för formen $n=O(D\beta )$ för enhetsintervallgrafer , tvådelade permutationsgrafer och kografer .

Beräkningskomplexitet

Beslutskomplexitet

Att bestämma om den metriska dimensionen för en graf som mest är ett givet heltal är NP-komplett. Det förblir NP-komplett för plana grafer med avgränsade grader , delade grafer , tvådelade grafer och deras komplement , linjediagram för tvådelade grafer, enhetsskivor , intervallgrafer med diameter 2 och permutationsgrafer med diameter 2, och grafer för avgränsad trädbredd .

För vilken fast konstant k som helst kan graferna med den metriska dimensionen som mest k kännas igen i polynomtid genom att testa alla möjliga k -tuplar av hörn, men denna algoritm är inte trakterbar med fast parameter (för den naturliga parametern k , lösningens storlek ). Genom att svara på en fråga som ställts av Lokshtanov (2010) , Hartung & Nichterlein (2013) visar att det metriska dimensionsbeslutsproblemet är komplett för den parametriserade komplexitetsklassen W[2], vilket antyder att en tidsgräns av formen n ^{O( k )} som uppnåtts med denna naiva algoritm är sannolikt optimal och att det är osannolikt att en hanteringsbar algoritm med fasta parametrar (för parametriseringen av k ) existerar. Ändå kan problemet lösas med fasta parametrar när det begränsas till intervallgrafer , och mer allmänt till grafer med avgränsad trädlängd, såsom kordagrafer , permutationsgrafer eller asteroid-trippelfria grafer.

Att bestämma om den metriska dimensionen för ett träd är högst ett givet heltal kan göras i linjär tid. Andra linjärtidsalgoritmer finns för kografer , kedjegrafer och kaktusblockgrafer (en klass som inkluderar både kaktusgrafer och blockgrafer ). Problemet kan lösas i polynomtid på ytterplanära grafer . Det kan också lösas i polynomtid för grafer av begränsat cyklomatiskt tal , men denna algoritm är återigen inte tolkbar med fasta parametrar (för parametern "cyklomatiskt tal") eftersom exponenten i polynomet beror på det cyklomatiska talet. Det finns algoritmer med fasta parametrar för att lösa det metriska dimensionsproblemet för parametrarna " vertex cover ", "max leaf number" och "modular width". Grafer med begränsat cyklomatiskt tal, vertextäckningsnummer eller max bladnummer har alla en begränsad trädbredd , men det är ett öppet problem att bestämma komplexiteten i det metriska dimensionsproblemet även på grafer med trädbredd 2, det vill säga serie-parallella grafer .

Approximationskomplexitet

Den metriska dimensionen av en godtycklig n -vertex-graf kan approximeras i polynomtid till inom ett approximationsförhållande på $2\log n$ genom att uttrycka det som ett uppsättningstäckningsproblem , ett problem med att täcka hela en given samling av element med så få uppsättningar som möjligt i en given familj av uppsättningar . I uppsättningstäckningsproblemet bildat av ett metriskt dimensionsproblem är de element som ska täckas ${\tbinom {n}{2}}$ paren av hörn som ska särskiljas och de mängder som kan täcka de är uppsättningarna av par som kan särskiljas av en enda vald vertex. Approximationsgränsen följer sedan genom att använda standardapproximationsalgoritmer för uppsättningstäckning. En alternativ girig algoritm som väljer hörn enligt skillnaden i entropi mellan ekvivalensklasserna av avståndsvektorer före och efter valet uppnår ett ännu bättre approximationsförhållande, $\log n+ \log \log _{2}n+1$ . Detta approximationsförhållande är nära bästa möjliga, eftersom under standardkomplexitetsteoretiska antaganden ett förhållande på $(1-\epsilon )\log n$ inte kan uppnås i polynomtid för någon $\epsilon >0$ . Den senare hårdheten av approximation gäller fortfarande för tillfällen begränsad till subkubiska grafer och till och med tvådelade subkubiska grafer.

Bibliografi

•   Beaudou, Laurent; Dankelmann, Peter; Foucaud, Florent; Henning, Michael A.; Mary, Arnaud; Parreau, Aline (2018), "Bounding the order of a graph using its diameter and metric dimension: a study through tree decompositions and VC dimension", SIAM Journal on Discrete Mathematics , 32 (2): 902–918, arXiv : 1610.01475 , doi : 10.1137/16M1097833 , S2CID 51882750
• Belmonte, R.; Fomin, FV; Golovach, PA; Ramanujan, MS (2015), "Metric dimension of bounded width graphs", i Italiano, GF; Pighizzini, G.; Sannella, DT (red.), Mathematical Foundations of Computer Science 2015 – MFCS 2015: 40th International Symposium, Milano, Italien, 24-28 augusti 2015, Proceedings , Lecture Notes in Computer Science , vol. 9235, Springer, s. 115–126, doi : 10.1007/978-3-662-48054-0_10 .
• Blumenthal, LM (1953), Theory and Applications of Distance Geometry , Clarendon, Oxford .
• Bonnet, E.; Purohit, N. (2019), "Metric Dimension Parameterized by Treewidth", i Jansen, BMP; Telle, JA (red.), Parameterized and Exact Computation 2019 – IPEC 2019: 14th International Symposium, Proceedings , Leibniz International Proceedings in Informatics (LIPIcs), vol. 148, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, s. 5:1-5:15, arXiv : 1907.08093 , doi : 10.4230/LIPIcs.IPEC.2019.5 .
•    Buczkowski, P.; Chartrand, G .; Poisson, C.; Zhang, P. (2003), "On k -dimensional graphs and their bases", Periodica Mathematica Hungarica , 46 (1): 9–15, doi : 10.1023/A:1025745406160 , MR 1975342 , S2CID 303 .
•   Chartrand, G .; Eroh, L.; Johnson, MA; Oellermann, OR (2000), "Resolvability in graphs and the metric dimension of a graph", Discrete Applied Mathematics , 105 (1–3): 99–113, doi : 10.1016/S0166-218X(00)00198-0 , hdl : 10338.dmlcz/127843 , MR 1780464 .
• Díaz, J.; Pottonen, O.; Serna, MJ; van Leeuwen, EJ (2012), "On the complexity of metric dimension" (PDF) , i Epstein, Leah; Ferragina, Paolo (red.), Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Slovenien, 10-12 september 2012, Proceedings , Lecture Notes in Computer Science, vol. 7501, Springer, s. 419–430, arXiv : 1107.2256 , doi : 10.1007/978-3-642-33090-2_37 .
•   Eppstein, David (2015), "Metric dimension parameterized by max leaf number", Journal of Graph Algorithms and Applications , 19 (1): 313–323, arXiv : 1506.01749 , doi : 10.7155/jgaa.00360 1328C6ID 1328C6ID .
• Epstein, Leah; Levin, Asaf; Woeginger, Gerhard J. (2012), "The (weighted) metric dimension of graphs: hard and easy case", i Golumbic, Martin Charles ; Stern, Michal; Levy, Avivit; et al. (red.), Graph-Theoretic Concepts in Computer Science: 38th International Workshop, WG 2012, Jerusalem, Israel, 26-28 juni 2012, Revised Selected Papers , Lecture Notes in Computer Science, vol. 7551, s. 114–125, doi : 10.1007/978-3-642-34611-8_14 .
• Feng, Min; Xu, Min; Wang, Kaishun (2013), "On the metric dimension of line graphs", Discrete Applied Mathematics , 161 ( 6): 802–805, arXiv : 1107.4140 , doi : 10.1016 /j.dam.2012.10.1018 3 , SC2018   .
• Fernau, Henning; Heggernes, Pinar ; van 't Hof, Pim; Meister, Daniel; Saei, Reza (2015), "Computing the metric dimension for chain graphs", Information Processing Letters , 115 (9): 671–676, doi : 10.1016/j.ipl.2015.04.006 .
•   Foucaud, Florent; Mertzios, George B.; Naserasr, Reza; Parreau, Aline; Valicov, Petru (2017a), "Identifiering, platsdomination och metrisk dimension på intervall- och permutationsgrafer. I. Bounds", Theoretical Computer Science , 68 : 43–58, arXiv : 1507.08164 , doi : 10.1016/j.1016/j. .006 , S2CID 25244200
•   Foucaud, Florent; Mertzios, George B.; Naserasr, Reza; Parreau, Aline; Valicov, Petru (2017b), "Identifiering, platsdominering och metrisk dimension på intervall- och permutationsgrafer. II. Algoritmer och komplexitet", Algorithmica , 78 ( 3 ) : 914–944, arXiv : 1405.2424 , doi : 5/00400. 016-0184-1 , S2CID 1520161 .
•   Garey, MR ; Johnson, DS (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness , WH Freeman, ISBN 0-7167-1045-5 A1.5: GT61, sid. 204.
•   Harary, F. ; Melter, RA (1976), "On the metric dimension of a graph", Ars Combinatoria , 2 : 191-195, MR 0457289 .
• Hartung, Sepp (2014), Exploring parameter spaces in coping with computational intractability, PhD avhandling , Technische Universität Berlin , hämtad 2015-09-15 .
•   Hartung, Sepp; Nichterlein, André (2013), "On the parameterized and approximation hardness of metric dimension", 2013 IEEE Conference on Computational Complexity (CCC), Stanford, CA, USA, 5-7 juni 2013, Proceedings , IEEE, s. 266– 276, arXiv : 1211.1636 , doi : 10.1109/CCC.2013.36 , S2CID 684505 .
•   Hauptmann, Mathias; Schmied, Richard; Viehmann, Claus (2012), "Approximation complexity of metric dimension problem", Journal of Discrete Algorithms , 14 : 214–222, doi : 10.1016/j.jda.2011.12.010 , MR 2922072 .
• Hernando, Carmen; Mora, Mercè; Pelayo, Ignacio M.; Seara, Carlos; Wood, David R. (2010), "Extremal graph theory for metric dimension and diameter" , Electronic Journal of Combinatorics , 17 : #R30, doi : 10.37236/302 .
• Hoffmann, Stefan; Elterman, Alina; Wanke, Egon (2016), "A linear time algorithm for metric dimension of cactus block graphs", Theoretical Computer Science , 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", i Bar-Noy, Amotz; Halldórsson, Magnús M. (red.), Algorithms for Sensor Systems: 8th International Symposium on Algorithms for Sensor Systems, Wireless Ad Hoc Networks and Autonomous Mobile Entities, ALGOSENSORS 2012, Ljubljana, Slovenia, September 13-14, 2012, Revised Selected Papers , Lecture Notes in Computer Science, vol. 7718, Springer, s. 90–92, arXiv : 1306.2187 , doi : 10.1007/978-3-642-36092-3_10 , S2CID 9740623 .
• Khuller, S .; Raghavachari, B.; Rosenfeld, A. (1996), "Landmarks in graphs", Discrete Applied Mathematics , 70 (3): 217–229, doi : 10.1016/0166-218x(95)00106-2 , hdl : 10338.dmlcz/ 10338.dmlcz/ 10702cz/10.1016 .
• Li, Shaohua; Pilipczuk, Marcin (juli 2022), "Hårdhet av metrisk dimension i grafer med konstant trädbredd", Algorithmica , 84 (11): 3110–3155, arXiv : 2102.09791 , doi : 10.1007/s025-y
• Lokshtanov, Daniel (2010), "Öppna problem – Parameteriserade komplexitets- och approximationsalgoritmer: Metrisk dimension", i Demaine, Erik D. ; Hajiaghayi, Mohammad Taghi; Marx, Dániel (red.), Parameterized Complexity and Approximation Algorithms , Dagstuhl Seminar Proceedings, Dagstuhl, Tyskland: Schloss Dagstuhl – Leibniz-Zentrum für Informatik .
•   Slater, PJ (1975), "Leaves of trees", Proc. 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Florida Atlantic Univ., Boca Raton, Fla., 1975) , Congressus Numerantium, vol. 14, Winnipeg: Utilitas Math., s. 549–559, MR 0422062 .
•   Slater, PJ (1988), "Dominerande och referensuppsättningar i en graf", Journal of Mathematical and Physical Sciences , 22 (4): 445–455, MR 0966610 .