En teoría de grafos , la dimensión métrica de un grafo G es la cardinalidad mínima de un subconjunto S de vértices de modo que todos los demás vértices estén determinados de forma única por sus distancias a los vértices en S. Encontrar la dimensión métrica de un grafo es un problema NP-completo ; la versión de decisión, que determina si la dimensión métrica es menor que un valor dado, es NP-completa .
Definición detallada
Para un subconjunto ordenado de vértices y un vértice v en un grafo conexo G , la representación de v con respecto a W es la k -tupla ordenada , donde d ( x , y ) representa la distancia entre los vértices x e y . El conjunto W es un conjunto resolutivo (o conjunto localizador) para G si cada dos vértices de G tienen representaciones distintas. La dimensión métrica de G es la cardinalidad mínima de un conjunto resolutivo para G . Un conjunto resolutivo que contiene un número mínimo de vértices se denomina base (o conjunto de referencia) para G . Los conjuntos resolutivos para grafos fueron introducidos independientemente por Slater (1975) y Harary & Melter (1976), mientras que el concepto de conjunto resolutivo y el de dimensión métrica fueron definidos mucho antes en el contexto más general de los espacios métricos por Blumenthal en su monografía Theory and Applications of Distance Geometry . Los grafos son ejemplos especiales de espacios métricos con su métrica de trayectoria intrínseca.
Árboles
Si un árbol es un camino, su dimensión métrica es uno. De lo contrario, sea L el conjunto de hojas, vértices de grado uno en el árbol. Sea K el conjunto de vértices que tienen grado mayor que dos, y que están conectados por caminos de vértices de grado dos a una o más hojas. Entonces la dimensión métrica es | L | − | K |. Una base de esta cardinalidad puede formarse quitando de L una de las hojas asociadas con cada vértice en K . [1] El mismo algoritmo es válido para el gráfico lineal del árbol, y por lo tanto cualquier árbol y su gráfico lineal tienen la misma dimensión métrica.
Propiedades
En Chartrand et al. (2000), se demuestra que:
- La dimensión métrica de un gráfico G es 1 si y sólo si G es una ruta.
- La dimensión métrica de un gráfico de n vértices es n − 1 si y solo si es un gráfico completo .
- La dimensión métrica de un gráfico de n vértices es n − 2 si y solo si el gráfico es un gráfico bipartito completo K s , t , un gráfico dividido o .
Relaciones entre el orden, la dimensión métrica y el diámetro
Khuller, Raghavachari y Rosenfeld (1996) demuestran la desigualdad para cualquier grafo de n vértices con diámetro y dimensión métrica . Estos límites se deducen del hecho de que cada vértice que no está en el conjunto de resolución está determinado de forma única por un vector de distancia de longitud, siendo cada entrada un entero entre 1 y (existen precisamente tales vectores). Sin embargo, el límite solo se logra para o ; el límite más preciso lo demuestran Hernando et al. (2010).
Para clases de grafos específicas, pueden cumplirse límites más pequeños. Por ejemplo, Beaudou et al. (2018) demostraron que para árboles (siendo el límite estricto para valores pares de D ), y un límite de la forma para grafos planos exteriores . Los mismos autores demostraron que para grafos sin grafo completo de orden t como menor y también dieron límites para grafos cordales y grafos de ancho de árbol acotado . Los autores Foucaud et al. (2017a) demostraron límites de la forma para grafos de intervalo y grafos de permutación , y límites de la forma para grafos de intervalo unitario , grafos de permutación bipartitos y cografos .
Complejidad computacional
Complejidad de decisiones
Decidir si la dimensión métrica de un gráfico es como máximo un entero dado es NP-completo. Sigue siendo NP-completo para gráficos planares de grado acotado , gráficos divididos , gráficos bipartitos y sus complementos , gráficos lineales de gráficos bipartitos, gráficos de disco unitario , gráficos de intervalo de diámetro 2 y gráficos de permutación de diámetro 2, ancho de árbol acotado .
Para cualquier constante fija k , los grafos de dimensión métrica como máximo k pueden reconocerse en tiempo polinomial , probando todas las k -tuplas posibles de vértices, pero este algoritmo no es manejable con parámetros fijos (para el parámetro natural k , el tamaño de la solución). Respondiendo a una pregunta planteada por Lokshtanov (2010), Hartung y Nichterlein (2013) muestran que el problema de decisión de dimensión métrica está completo para la clase de complejidad parametrizada W[2], lo que implica que un límite de tiempo de la forma n O( k ) como el logrado por este algoritmo ingenuo es probablemente óptimo y que es poco probable que exista un algoritmo manejable con parámetros fijos (para la parametrización por k ). Sin embargo, el problema se vuelve manejable con parámetros fijos cuando se restringe a grafos de intervalos , y, más generalmente, a grafos de longitud de árbol acotada, como grafos cordales , grafos de permutación o grafos asteroidales-triples-libres.
Decidir si la dimensión métrica de un árbol es como máximo un entero dado se puede hacer en tiempo lineal [10] Existen otros algoritmos de tiempo lineal para cografos , grafos de cadena , y grafos de bloques de cactus (una clase que incluye tanto grafos de cactus como grafos de bloques ). El problema se puede resolver en tiempo polinomial en grafos planos exteriores . También se puede resolver en tiempo polinomial para grafos de número ciclomático acotado , pero este algoritmo nuevamente no es manejable con parámetros fijos (para el parámetro "número ciclomático") porque el exponente en el polinomio depende del número ciclomático. Existen algoritmos manejables con parámetros fijos para resolver el problema de dimensión métrica para los parámetros " cobertura de vértices ", "número máximo de hojas", y "ancho modular". Los gráficos con número ciclomático acotado, número de cobertura de vértices o número máximo de hojas tienen todos un ancho de árbol acotado , sin embargo es un problema abierto determinar la complejidad del problema de dimensión métrica incluso en gráficos con un ancho de árbol 2, es decir, gráficos en serie-paralelos .
Complejidad de aproximación
La dimensión métrica de un gráfico arbitrario de n vértices puede aproximarse en tiempo polinomial a una razón de aproximación de expresándola como un problema de cobertura de conjuntos , un problema de cubrir toda una colección dada de elementos con la menor cantidad posible de conjuntos en una familia dada de conjuntos . En el problema de cobertura de conjuntos formado a partir de un problema de dimensión métrica, los elementos a cubrir son los pares de vértices a distinguir, y los conjuntos que pueden cubrirlos son los conjuntos de pares que pueden distinguirse por un único vértice elegido. El límite de aproximación se obtiene aplicando algoritmos de aproximación estándar para la cobertura de conjuntos. Un algoritmo voraz alternativo que elige vértices según la diferencia de entropía entre las clases de equivalencia de vectores de distancia antes y después de la elección logra una razón de aproximación incluso mejor, . Esta razón de aproximación es cercana a la mejor posible, ya que bajo supuestos teóricos de complejidad estándar no se puede lograr una razón de en tiempo polinomial para ningún . La última dureza de aproximación todavía se mantiene para casos restringidos a gráficos subcúbicos, e incluso a gráficos subcúbicos bipartitos .
Referencias
Notas
- ^ Slater 1975; Harary y Melter 1976; Khuller, Raghavachari y Rosenfeld 1996. Nótese la definición no estándar de Slater de las hojas de un árbol.
- ^ Más tarde 1975; Harary y Melter 1976.
Bibliografía
- Beaudou, Laurent; Dankelmann, Peter; Foucaud, Florent; Henning, Michael A.; Mary, Arnaud; Parreau, Aline (2018), "Delimitación del orden de un gráfico utilizando su diámetro y dimensión métrica: un estudio a través de descomposiciones de árboles y dimensión VC", 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", en Italiano, GF; Pighizzini, G.; Sannella, DT (eds.), Mathematical Foundations of Computer Science 2015 – MFCS 2015: 40th International Symposium, Milán, Italia, 24-28 de agosto de 2015, Actas , Lecture Notes in Computer Science , vol. 9235, Springer, págs. 115–126, doi :10.1007/978-3-662-48054-0_10, ISBN 978-3-662-48053-3.
- Blumenthal, LM (1953), Teoría y aplicaciones de la geometría de distancias , Clarendon, Oxford.
- Bonnet, E.; Purohit, N. (2019), "Dimensión métrica parametrizada por ancho de árbol", en Jansen, BMP; Telle, JA (eds.), Cálculo parametrizado y exacto 2019 – IPEC 2019: 14.º simposio internacional, Actas , Leibniz International Proceedings in Informatics (LIPIcs), vol. 148, Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, págs. 5:1–5:15, arXiv : 1907.08093 , doi : 10.4230/LIPIcs.IPEC.2019.5.
- Buczkowski, P.; Chartrand, G .; Poisson, C.; Zhang, P. (2003), "Sobre gráficos k -dimensionales y sus bases", Periodica Mathematica Hungarica , 46 (1): 9–15, doi :10.1023/A:1025745406160, MR 1975342, S2CID 33390310.
- Chartrand, G. ; Eroh, L.; Johnson, MA; Oellermann, OR (2000), "Resolubilidad en grafos y la dimensión métrica de un grafo", 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), "Sobre la complejidad de la dimensión métrica" (PDF) , en Epstein, Leah; Ferragina, Paolo (eds.), Algorithms – ESA 2012: 20th Annual European Symposium, Ljubljana, Eslovenia, 10-12 de septiembre de 2012, Actas , Lecture Notes in Computer Science, vol. 7501, Springer, págs. 419–430, arXiv : 1107.2256 , doi :10.1007/978-3-642-33090-2_37, ISBN 978-3-642-33089-6.
- Eppstein, David (2015), "Dimensión métrica parametrizada por el número máximo de hojas", 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), "La dimensión métrica (ponderada) de los grafos: casos difíciles y fáciles", en Golumbic, Martin Charles ; Stern, Michal; Levy, Avivit; et al. (eds.), Graph-Theoretic Concepts in Computer Science: 38th International Workshop, WG 2012, Jerusalén, Israel, 26-28 de junio de 2012, Documentos revisados seleccionados, Lecture Notes in Computer Science, vol. 7551, págs. 114-125, doi :10.1007/978-3-642-34611-8_14, ISBN 978-3-642-34610-1.
- Feng, Min; Xu, Min; Wang, Kaishun (2013), "Sobre la dimensión métrica de los gráficos de líneas", Discrete Applied Mathematics , 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), "Cálculo de la dimensión métrica para gráficos de cadena", 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), "Identificación, dominación de la ubicación y dimensión métrica en gráficos de intervalos y permutaciones. I. Límites", Theoretical Computer Science , 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), "Identificación, dominación de la ubicación y dimensión métrica en gráficos de intervalos y permutaciones. II. Algoritmos y complejidad", Algorithmica , 78 (3): 914–944, arXiv : 1405.2424 , doi :10.1007/s00453-016-0184-1, S2CID 1520161.
- Garey, MR ; Johnson, DS (1979), Computadoras e intratabilidad: una guía para la teoría de la NP-completitud , WH Freeman, ISBN 0-7167-1045-5A1.5: GT61, pág. 204.
- Harary, F. ; Melter, RA (1976), "Sobre la dimensión métrica de un gráfico", Ars Combinatoria , 2 : 191–195, MR 0457289.
- Hartung, Sepp (2014), Explorando espacios de parámetros para afrontar la intratabilidad computacional, tesis doctoral, Technische Universität Berlin , consultado el 15 de septiembre de 2015..
- Hartung, Sepp; Nichterlein, André (2013), "Sobre la dureza parametrizada y de aproximación de la dimensión métrica", 2013 IEEE Conference on Computational Complexity (CCC), Stanford, CA, EE. UU., 5-7 de junio de 2013, Actas , IEEE, págs. 266–276, arXiv : 1211.1636 , doi :10.1109/CCC.2013.36, ISBN 978-0-7695-4997-2, S2CID684505 .
- Hauptmann, Mathías; Schmied, Richard; Viehmann, Claus (2012), "Complejidad de aproximación del problema de dimensión métrica", 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), "Teoría de grafos extremos para dimensiones y diámetros métricos", Electronic Journal of Combinatorics , 17 : #R30, doi : 10.37236/302 , hdl : 2117/8261.
- Hoffmann, Stefan; Elterman, Alina; Wanke, Egon (2016), "Un algoritmo de tiempo lineal para la dimensión métrica de gráficos de bloques de cactus", Theoretical Computer Science , 630 : 43–62, doi : 10.1016/j.tcs.2016.03.024
- Hoffmann, Stefan; Wanke, Egon (2013), "La dimensión métrica para los gráficos de discos unitarios de Gabriel es NP-completa", en Bar-Noy, Amotz; Halldórsson, Magnús M. (eds.), Algoritmos para sistemas de sensores: 8.º simposio internacional sobre algoritmos para sistemas de sensores, redes ad hoc inalámbricas y entidades móviles autónomas, ALGOSENSORS 2012, Liubliana, Eslovenia, 13 y 14 de septiembre de 2012, Documentos seleccionados revisados , Lecture Notes in Computer Science, vol. 7718, Springer, págs. 90–92, arXiv : 1306.2187 , doi :10.1007/978-3-642-36092-3_10, ISBN 978-3-642-36091-6, Número de identificación del sujeto 9740623.
- Khuller, S .; Raghavachari, B.; Rosenfeld, A. (1996), "Puntos de referencia en gráficos", Discrete Applied Mathematics , 70 (3): 217–229, doi :10.1016/0166-218x(95)00106-2, hdl : 10338.dmlcz/140702.
- Li, Shaohua; Pilipczuk, Marcin (julio de 2022), "Dureza de la dimensión métrica en gráficos de ancho de árbol constante", Algorithmica , 84 (11): 3110–3155, arXiv : 2102.09791 , doi : 10.1007/s00453-022-01005-y, S2CID 231979414
- Lokshtanov, Daniel (2010), "Problemas abiertos: algoritmos de aproximación y complejidad parametrizados: dimensión métrica", en Demaine, Erik D .; Hajiaghayi, Mohammad Taghi; Marx, Dániel (eds.), Algoritmos de aproximación y complejidad parametrizada, Actas del seminario de Dagstuhl, Dagstuhl, Alemania: Schloss Dagstuhl – Leibniz-Zentrum für Informatik , doi : 10.4230/DagSemProc.09511.3.
- Slater, PJ (1975), "Hojas de árboles", Proc. 6th Southeastern Conference on Combinatorics, Graph Theory, and Computing (Universidad Atlántica de Florida, Boca Raton, Fla., 1975) , Congressus Numerantium, vol. 14, Winnipeg: Utilitas Math., págs. 549–559, MR 0422062.
- Slater, PJ (1988), "Conjuntos dominantes y de referencia en un gráfico", Journal of Mathematical and Physical Sciences , 22 (4): 445–455, MR 0966610.