Metrische Dimension (Graphentheorie) – Wikipedia

In der Graphentheorie ist die metrische Dimension eines Graphen G ist die minimale Kardinalität einer Teilmenge S. von Scheitelpunkten, so dass alle anderen Scheitelpunkte eindeutig durch ihre Abstände zu den Scheitelpunkten in bestimmt werden S.. Das Ermitteln der metrischen Dimension eines Graphen ist ein NP-schwieriges Problem. Die Entscheidungsversion, die bestimmt, ob die metrische Dimension kleiner als ein bestimmter Wert ist, ist NP-vollständig.

Detaillierte Definition[edit]

Für eine geordnete Teilmenge

${ displaystyle W = {w_ {1}, w_ {2}, dots, w_ {k} }}$

von Eckpunkten und einem Eckpunkt v in einem zusammenhängenden Graphen G, die Darstellung von v in Gedenken an W. ist die bestellt k-Tupel

${ displaystyle r (v | W) = (d (v, w_ {1}), d (v, w_ {2}), dots, d (v, w_ {k}))}$

, wo d((x,y) repräsentiert den Abstand zwischen den Eckpunkten x und y. Der Satz W. ist ein Auflösungssatz (oder ein Ortungssatz) für G wenn alle zwei Eckpunkte von G haben unterschiedliche Darstellungen. Die metrische Dimension von G ist die minimale Kardinalität eines Auflösungssatzes für G. Eine Auflösungsmenge, die eine minimale Anzahl von Eckpunkten enthält, wird als Basis (oder Referenzmenge) für bezeichnet G. Auflösungsmengen für Graphen wurden von Slater (1975) und Harary & Melter (1976) unabhängig voneinander eingeführt, während das Konzept einer Auflösungsmenge und das der metrischen Dimension im allgemeineren Kontext metrischer Räume von Blumenthal in seiner Monographie viel früher definiert wurden Theorie und Anwendungen der Distanzgeometrie. Diagramme sind spezielle Beispiele für metrische Räume mit ihrer intrinsischen Pfadmetrik.

Slater (1975) (siehe auch Harary & Melter (1976) und Khuller, Raghavachari & Rosenfeld (1996)) liefert die folgende einfache Charakterisierung der metrischen Dimension eines Baumes. Wenn der Baum ein Pfad ist, ist seine metrische Dimension eins. Ansonsten lass L. bezeichnen die Menge der Eckpunkte ersten Grades im Baum (normalerweise Blätter genannt, obwohl Slater dieses Wort anders verwendet). Lassen K. sei die Menge von Scheitelpunkten, deren Grad größer als zwei ist und die durch Pfade von Scheitelpunkten zweiten Grades mit einem oder mehreren Blättern verbunden sind. Dann ist die metrische Dimension |L.| – |K.|. Eine Basis dieser Kardinalität kann durch Entfernen von gebildet werden L. eines der Blätter, die jedem Scheitelpunkt in zugeordnet sind K.. Der gleiche Algorithmus gilt für das Liniendiagramm des Baums, wie von Feng, Xu & Wang (2013) bewiesen (und daher haben jeder Baum und sein Liniendiagramm dieselbe metrische Dimension).

Eigenschaften[edit]

In Chartrand et al. (2000) ist bewiesen, dass:

• Die metrische Dimension eines Diagramms G ist 1 genau dann, wenn G ist ein Weg.
• Die metrische Dimension eines n-Vertex-Graph ist n – 1 genau dann, wenn es sich um ein vollständiges Diagramm handelt.
• Die metrische Dimension eines n-Vertex-Graph ist n – 2 genau dann, wenn der Graph ein vollständiger zweigliedriger Graph ist K._{s, t}, ein geteiltes Diagramm
  ${ displaystyle K_ {s} + { overline {K_ {t}}} (s geq 1, t geq 2)}$

  , oder

  ${ displaystyle K_ {s} + (K_ {1} cup K_ {t}) (s, t geq 1)}$

  .

Beziehungen zwischen der Reihenfolge, der metrischen Abmessung und dem Durchmesser[edit]

Khuller, Raghavachari & Rosenfeld (1996) beweisen die Ungleichheit

${ displaystyle n leq D ^ { beta} + beta}$

für jeden n-Vertex-Diagramm mit Durchmesser D. und metrische Dimension β. Diese Grenzen ergeben sich aus der Tatsache, dass jeder Scheitelpunkt, der nicht in der Auflösungsmenge enthalten ist, eindeutig durch einen Abstandsvektor der Länge β bestimmt wird, wobei jeder Eintrag eine ganze Zahl zwischen 1 und 1 ist D. (es gibt genau

${ displaystyle D ^ { beta}}$

solche Vektoren). Die Grenze wird jedoch nur für erreicht

${ displaystyle D leq 3}$

oder

${ displaystyle beta = 1}$

;; die genauere Bindung

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

wird von Hernando et al. (2010).

Für bestimmte Diagrammklassen können kleinere Grenzen gelten. Zum Beispiel haben Beaudou et al. (2018) haben das bewiesen

${ displaystyle n leq ( beta D + 4) (D + 2) / 8}$

für Bäume (die Grenze ist eng für gerade Werte von D.) und eine Grenze der Form

${ displaystyle n = O (D ^ {2} beta)}$

für äußere ebene Graphen. Die gleichen Autoren haben das bewiesen

${ displaystyle n leq (D beta +1) ^ {t-1}}$

für Diagramme ohne vollständiges Diagramm der Reihenfolge t als Moll und gab auch Grenzen für Akkordgraphen und Graphen der begrenzten Baumbreite. Die Autoren Foucaud et al. (2017a) haben Grenzen der Form bewiesen

${ displaystyle n = O (D beta ^ {2})}$

für Intervalldiagramme und Permutationsdiagramme sowie Grenzen des Formulars

${ displaystyle n = O (D beta)}$

für Einheitsintervallgraphen, zweigliedrige Permutationsgraphen und Cographien.

Rechenkomplexität[edit]

Entscheidungskomplexität[edit]

Die Entscheidung, ob die metrische Dimension eines Graphen höchstens eine bestimmte Ganzzahl ist, ist NP-vollständig (Garey & Johnson 1979). Es bleibt NP-vollständig für planare Graphen mit begrenztem Grad (Díaz et al. 2012), geteilte Graphen, zweigliedrige Graphen und ihre Ergänzungen, Liniendiagramme von zweigliedrigen Graphen (Epstein, Levin & Woeginger 2012), Einheitsscheibendiagramme (Hoffmann & Wanke 2012) ), Intervallgraphen von Durchmesser 2 und Permutationsgraphen von Durchmesser 2 (Foucaud et al. 2017b).

Für jede feste Konstante k, die Diagramme der metrischen Dimension höchstens k kann in Polynomzeit erkannt werden, indem alle möglichen getestet werden k-Tupel von Eckpunkten, aber dieser Algorithmus ist nicht mit festen Parametern nachvollziehbar (für den natürlichen Parameter k, die Lösungsgröße). Die Beantwortung einer Frage von Lokshtanov (2010), Hartung & Nichterlein (2013) zeigt, dass das Entscheidungsproblem für die metrische Dimension für die parametrisierte Komplexitätsklasse W vollständig ist[2], was bedeutet, dass eine Zeit an die Form gebunden ist n^Ö(k) wie durch diesen naiven Algorithmus erreicht, ist wahrscheinlich optimal und dass ein fester Parameter verfolgbarer Algorithmus (für die Parametrisierung durch k) ist unwahrscheinlich. Trotzdem lässt sich das Problem mit festen Parametern lösen, wenn es auf Intervallgraphen (Foucaud et al. 2017b) und allgemein auf Graphen mit begrenzter Baumlänge (Belmonte et al. 2015) wie Akkordgraphen, Permutationsgraphen oder Asteroidengraphen beschränkt ist. dreifach freie Graphen.

Die Entscheidung, ob die metrische Dimension eines Baums höchstens eine bestimmte Ganzzahl ist, kann in linearer Zeit erfolgen (Slater 1975; Harary & Melter 1976). Andere lineare Zeitalgorithmen existieren für Cographen (Epstein, Levin & Woeginger 2012), Kettengraphen (Fernau et al. 2015) und Kaktusblockgraphen (Hoffmann, Elterman & Wanke 2016) (eine Klasse, die sowohl Kaktusgraphen als auch Blockgraphen umfasst). Das Problem kann in der Polynomzeit auf äußeren planaren Graphen gelöst werden (Díaz et al. 2012). Es kann auch in Polynomzeit für Graphen mit begrenzter zyklomatischer Zahl gelöst werden (Epstein, Levin & Woeginger 2012), aber dieser Algorithmus ist wiederum nicht mit festen Parametern nachvollziehbar (für den Parameter) “zyklomatische Zahl”) weil der Exponent im Polynom von der zyklomatischen Zahl abhängt. Es gibt nachvollziehbare Algorithmen mit festen Parametern, um das Problem der metrischen Dimension für die Parameter zu lösen “Scheitelpunktabdeckung” (Hartung & Nichterlein 2013), “maximale Blattzahl” (Eppstein 2015) und “modulare Breite” (Belmonte et al. 2015). Diagramme mit begrenzter zyklomatischer Zahl, Scheitelpunktabdeckungsnummer oder maximaler Blattzahl haben alle eine begrenzte Baumbreite. Es ist jedoch ein offenes Problem, die Komplexität des metrischen Dimensionsproblems selbst auf Diagrammen der Baumbreite 2 zu bestimmen, d. H. Serienparallelen Diagrammen (Belmonte et al. 2015).

Annäherungskomplexität[edit]

Die metrische Dimension eines beliebigen n-Vertexgraph kann in Polynomzeit auf ein Näherungsverhältnis von angenähert werden

${ displaystyle 2 log n}$

indem es als Set-Cover-Problem ausgedrückt wird, ein Problem, bei dem eine bestimmte Sammlung von Elementen durch möglichst wenige Sets in einer bestimmten Set-Familie abgedeckt wird (Khuller, Raghavachari & Rosenfeld 1996). In dem Satzdeckungsproblem, das aus einem metrischen Dimensionsproblem gebildet wird, sind die zu behandelnden Elemente die

${ displaystyle { tbinom {n} {2}}}$

zu unterscheidende Scheitelpunktpaare und die Mengen, die sie abdecken können, sind die Sätze von Paaren, die durch einen einzelnen ausgewählten Scheitelpunkt unterschieden werden können. Die Approximationsgrenze folgt dann durch Anwendung von Standard-Approximationsalgorithmen für die Set-Abdeckung. Ein alternativer Greedy-Algorithmus, der Eckpunkte entsprechend der Entropiedifferenz zwischen den Äquivalenzklassen von Distanzvektoren vor und nach der Auswahl auswählt, erzielt ein noch besseres Approximationsverhältnis.

${ displaystyle log n + log log _ {2} n + 1}$

(Hauptmann, Schmied & Viehmann 2012). Dieses Näherungsverhältnis ist nahezu bestmöglich, da unter standardmäßigen komplexitätstheoretischen Annahmen ein Verhältnis von

${ displaystyle (1- epsilon) log n}$

kann für keine in Polynomzeit erreicht werden

${ displaystyle epsilon> 0}$

Verweise[edit]

• Beaudou, Laurent; Dankelmann, Peter; Foucaud, Florent; Henning, Michael A.; Mary, Arnaud; Parreau, Aline (2018), “Begrenzung der Reihenfolge eines Graphen anhand seines Durchmessers und seiner metrischen Dimension: eine Studie über Baumzerlegungen und VC-Dimensionen”, 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), “Metrische Abmessung von Diagrammen mit begrenzter Breite”in Italiano, GF; Pighizzini, G.; Sannella, DT (Hrsg.), Mathematische Grundlagen der Informatik 2015 – MFCS 2015: 40. Internationales Symposium, Mailand, Italien, 24.-28. August 2015, Proceedings, Lecture Notes in Computer Science, 9235Springer, S. 115–126, doi:10.1007 / 978-3-662-48054-0_10.
• Blumenthal, LM (1953), Theorie und Anwendungen der Distanzgeometrie, Clarendon, Oxford.
• Buczkowski, P.; Chartrand, G.; Poisson, C.; Zhang, P. (2003), “Auf k-dimensionale Graphen und ihre Grundlagen”, Periodica Mathematica Hungarica, 46 (1): 9–15, doi:10.1023 / A: 1025745406160, HERR 1975342, S2CID 33390310.
• Chartrand, G.; Eroh, L.; Johnson, MA; Oellermann, OR (2000), “Auflösbarkeit in Diagrammen und die metrische Dimension eines Diagramms”, Diskrete Angewandte Mathematik, 105 (1–3): 99–113, doi:10.1016 / S0166-218X (00) 00198-0, hdl:10338.dmlcz / 127843, HERR 1780464.
• Díaz, J.; Pottonen, O.; Serna, MJ; van Leeuwen, EJ (2012), “Zur Komplexität der metrischen Dimension” (PDF)in Epstein Leah; Ferragina, Paolo (Hrsg.), Algorithmen – ESA 2012: 20. Europäisches Jahressymposium, Ljubljana, Slowenien, 10.-12. September 2012, Proceedings, Lecture Notes in Computer Science, 7501Springer, S. 419–430, arXiv:1107,2256, doi:10.1007 / 978-3-642-33090-2_37.
• Eppstein, David (2015), “Metrische Dimension, parametrisiert durch die maximale Blattzahl”, 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), “Die (gewichtete) metrische Dimension von Diagrammen: schwierige und einfache Fälle”in Golumbic Martin Charles; Stern, Michal; Levy, Avivit; et al. (Hrsg.), Graphentheoretische Konzepte in der Informatik: 38. Internationaler Workshop, WG 2012, Jerusalem, Israel, 26.-28. Juni 2012, überarbeitete ausgewählte Artikel, Lecture Notes in Computer Science, 7551S. 114–125, doi:10.1007 / 978-3-642-34611-8_14.
• Feng, Min; Xu, Min; Wang, Kaishun (2013), “Auf der metrischen Dimension von Liniendiagrammen”, Diskrete Angewandte Mathematik, 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), “Berechnung der metrischen Dimension für Kettengraphen”, Informationsverarbeitungsbriefe, 115 (9): 671–676, doi:10.1016 / j.ipl.2015.04.006.
• Foucaud, Florent; Mertzios, George B.; Naserasr, Reza; Parreau, Aline; Valicov, Petru (2017a), “Identifizierung, Standortdominanz und metrische Dimension in Intervall- und Permutationsgraphen. I. Grenzen”, Theoretische Informatik, 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), “Identifizierung, Standortdominanz und metrische Dimension in Intervall- und Permutationsgraphen. II. Algorithmen und Komplexität”, Algorithmica, 78 (3): 914–944, arXiv:1405.2424, doi:10.1007 / s00453-016-0184-1, S2CID 1520161.
• Garey, MR; Johnson, DS (1979), Computer und Intraktabilität: Ein Leitfaden zur Theorie der NP-Vollständigkeit, WH Freeman, ISBN 0-7167-1045-5 A1.5: GT61, p. 204.
• Harary, F.; Melter, RA (1976), “Auf der metrischen Dimension eines Diagramms”, Ars Combinatoria, 2: 191–195, MR 0457289.
• Hartung, Sepp (2014), Erforschung von Parameterräumen im Umgang mit rechnerischer Unlösbarkeit, DissertationTechnische Universität Berlinabgerufen 2015-09-15.
• Hartung, Sepp; Nichterlein, André (2013), “Zur parametrisierten und approximativen Härte der metrischen Dimension”, 2013 IEEE-Konferenz über 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), “Approximationskomplexität des metrischen Dimensionsproblems”, Journal of Discrete Algorithms, 14: 214–222, doi:10.1016 / j.jda.2011.12.010, HERR 2922072.
• Hernando, Carmen; Mora, Mercè; Pelayo, Ignacio M.; Seara, Carlos; Wood, David R. (2010), “Extremalgraphentheorie für metrische Dimension und Durchmesser”, Elektronisches Journal für Kombinatorik, 17: # R30, doi:10.37236 / 302.
• Hoffmann, Stefan; Elterman, Alina; Wanke, Egon (2016), “Ein linearer Zeitalgorithmus für die metrische Dimension von Kaktusblockgraphen”, Theoretische Informatik, 630: 43–62, doi:10.1016 / j.tcs.2016.03.024
• Hoffmann, Stefan; Wanke, Egon (2012), “Die metrische Dimension für Gabriel Unit Disk-Diagramme ist NP-vollständig”in Bar-Noy Amotz; Halldórsson, Magnús M. (Hrsg.), Algorithmen für Sensorsysteme: 8. Internationales Symposium zu Algorithmen für Sensorsysteme, drahtlose Ad-hoc-Netzwerke und autonome mobile Einheiten, ALGOSENSORS 2012, Ljubljana, Slowenien, 13.-14. September 2012, überarbeitete ausgewählte Artikel, Lecture Notes in Computer Science, 7718Springer, S. 90–92, arXiv:1306.2187, doi:10.1007 / 978-3-642-36092-3_10, S2CID 9740623.
• Khuller, S.; Raghavachari, B.; Rosenfeld, A. (1996), “Orientierungspunkte in Grafiken”, Diskrete Angewandte Mathematik, 70 (3): 217–229, doi:10.1016 / 0166-218x (95) 00106-2, hdl:10338.dmlcz / 140702.
• Lokshtanov, Daniel (2010), “Offene Probleme – Parametrisierte Komplexitäts- und Approximationsalgorithmen: Metrische Dimension”in Demaine Erik D.; Hajiaghayi, MohammadTaghi; Marx, Dániel (Hrsg.), Parametrisierte Komplexitäts- und Approximationsalgorithmen, Dagstuhl Seminar Proceedings, Dagstuhl, Deutschland: Schloss Dagstuhl – Leibniz-Zentrum für Informatik.
• Slater, PJ (1975), “Blätter von Bäumen”, Proc. 6. Südöstliche Konferenz über Kombinatorik, Graphentheorie und Computing (Florida Atlantic Univ., Boca Raton, Florida, 1975), Congressus Numerantium, 14, Winnipeg: Utilitas Math., S. 549–559, MR 0422062.
• Slater, PJ (1988), “Dominierende und Referenzsätze in einem Diagramm”, Zeitschrift für Mathematik und Physik, 22 (4): 445–455, MR 0966610.