En la teoría de grafos , la métrica de la dimensión de un gráfico G es la cardinalidad mínima de un subconjunto S de vértices de tal manera que todos los otros vértices se determinan de forma única por sus distancias a los vértices en S . Encontrar la dimensión métrica de una gráfica es un problema NP-difícil ; 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 gráfico conectado G , la representación de v con respecto a W es la tupla k ordenada, Donde d ( x , y ) representa la distancia entre los vértices x y y . El conjunto W es un conjunto de resolución (o conjunto de localización) 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 de resolución para G . Un conjunto resolver que contiene un número mínimo de vértices se llama una base (o conjunto de referencia) para G . Slater (1975) y Harary & Melter (1976) introdujeron de forma independiente conjuntos de resolución para gráficos , mientras que el concepto de conjunto de resolución y el de dimensión métrica fueron definidos mucho antes en el contexto más general de espacios métricos por Blumenthal en su monografía Theory y Aplicaciones de la Geometría de Distancia . Los gráficos son ejemplos especiales de espacios métricos con su métrica de ruta intrínseca.
Árboles
Slater (1975) (ver también Harary & Melter (1976) y Khuller, Raghavachari & Rosenfeld (1996) ) proporciona la siguiente caracterización simple de la dimensión métrica de un árbol . Si el árbol es un camino, su dimensión métrica es uno. De lo contrario, deje que L denote el conjunto de vértices de grado uno en el árbol (generalmente llamados hojas, aunque Slater usa esa palabra de manera diferente). Sea K el conjunto de vértices que tienen un 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 |. A base de esta cardinalidad puede estar formado mediante la eliminación de L una de las hojas asociadas con cada vértice en K . El mismo algoritmo es válido para el gráfico de líneas del árbol, como lo demostraron Feng, Xu y Wang (2013) (y por lo tanto, cualquier árbol y su gráfico de líneas tienen la misma dimensión métrica).
Propiedades
En Chartrand et al. (2000) , se comprueba que:
- La dimensión métrica de un gráfico G es 1 si y solo 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 pedido, la dimensión métrica y el diámetro
Khuller, Raghavachari y Rosenfeld (1996) prueban la desigualdadpara cualquier gráfico n -vertex con diámetro D y dimensión métrica β. Estos límites se derivan 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 número entero entre 1 y D (hay precisamentetales vectores). Sin embargo, el límite solo se logra para o ; el límite más precisoestá probado por Hernando et al. (2010) .
Para clases de gráficos específicas, se pueden mantener límites más pequeños. Por ejemplo, Beaudou et al. (2018) demostró quepara árboles (el límite es estrecho para valores pares de D ), y un límite de la formapara gráficos planos exteriores . Los mismos autores demostraron quepara gráficos sin un gráfico completo de orden t como menor y también dio límites para los gráficos cordales y los gráficos de ancho de árbol acotado . Los autores Foucaud et al. (2017a) límites comprobados de la formapara gráficos de intervalo y gráficos de permutación , y límites de la formapara gráficos de intervalo unitario, gráficos de permutación bipartita y cografías .
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 ( Garey & Johnson 1979 ). Queda NP-completo para el grado limitado grafos planos ( Díaz et al. 2012 ), gráficos de división , gráficos bipartitos y sus complementos , gráficos de líneas de grafos bipartitos ( Epstein, Levin y Woeginger 2012 ), gráficos de disco unidad ( Hoffmann & Wanke 2012 ), gráficos de intervalo de diámetro 2 y gráficos de permutación de diámetro 2 ( Foucaud et al.2017b ).
Para cualquier constante fija k , las gráficas de dimensión métrica como máximo k pueden reconocerse en tiempo polinomial , probando todas las k -tuplas de vértices posibles , pero este algoritmo no es tratable 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 & 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 logrado mediante este algoritmo ingenuo es probable que sea óptimo y que es poco probable que exista un algoritmo manejable de parámetros fijos (para la parametrización por k ). Sin embargo, el problema se vuelve manejable con parámetros fijos cuando se restringe a gráficos de intervalo ( Foucaud et al. 2017b ), y más generalmente a gráficos de longitud de árbol acotada ( Belmonte et al. 2015 ), como gráficos de cuerdas , gráficos de permutación o gráficos de asteroides. gráficos de triple libre.
Decidir si la dimensión métrica de un árbol es como máximo un entero dado se puede hacer en tiempo lineal ( Slater 1975 ; Harary & Melter 1976 ). Existen otros algoritmos en tiempo lineal para cographs ( Epstein, Levin y Woeginger 2012 ), gráficos de cadena ( Fernau et al. 2015 ) y gráficos de bloques de cactus ( Hoffmann, Elterman y Wanke 2016 ) (una clase incluyendo tanto los gráficos de cactus y gráficos de bloques ). El problema puede resolverse en tiempo polinomial en gráficos planos exteriores ( Díaz et al. 2012 ). También se puede resolver en tiempo polinomial para gráficas de número ciclomático acotado ( Epstein, Levin & Woeginger 2012 ), 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 de el número ciclomático. Existen algoritmos manejables de parámetros fijos para resolver el problema de la dimensión métrica para los parámetros " cobertura de vértice " ( Hartung & Nichterlein 2013 ), "número máximo de hojas" ( Eppstein 2015 ) y "ancho modular" ( Belmonte et al. 2015 ). Todos los gráficos con número ciclomático acotado, número de cobertura de vértice o número máximo de hojas tienen ancho de árbol acotado , sin embargo, es un problema abierto determinar la complejidad del problema de dimensión métrica incluso en gráficos de ancho de árbol 2, es decir, gráficos en serie-paralelos ( Belmonte et al.2015 ). En el lado negativo de los valores generales del ancho del árbol, se demostró que el problema es W [1] -hard cuando se parametriza por el ancho de la ruta (y por lo tanto, también por el ancho del árbol) del gráfico de entrada ( Bonnet & Purohit 2019 ).
Complejidad de aproximación
La dimensión métrica de un gráfico arbitrario de n -vértices puede aproximarse en tiempo polinomial dentro de una relación de aproximación deexpresándolo como un problema de cobertura de conjuntos , un problema de cubrir toda una colección dada de elementos con el menor número posible de conjuntos en una familia de conjuntos dada ( Khuller, Raghavachari & Rosenfeld 1996 ). En el problema de cobertura de conjuntos formado a partir de un problema de dimensión métrica, los elementos a cubrir son lospares 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 sigue luego mediante la aplicación de algoritmos de aproximación estándar para la cobertura del conjunto. Un algoritmo codicioso alternativo que elige vértices de acuerdo con la diferencia de entropía entre las clases de equivalencia de los vectores de distancia antes y después de la elección logra una relación de aproximación aún mejor,( Hauptmann, Schmied y Viehmann 2012 ). Esta relación de aproximación es cercana a la mejor posible, ya que bajo supuestos estándar de teoría de la complejidad una relación de no se puede lograr en tiempo polinomial para ninguna ( Hauptmann, Schmied y Viehmann 2012 ). La última dureza de aproximación sigue siendo válida para instancias restringidas a gráficos subcúbicos ( Hartung & Nichterlein 2013 ), e incluso a gráficos subcúbicos bipartitos como se muestra en la tesis doctoral de Hartung ( Hartung 2014 ).
Referencias
- Beaudou, Laurent; Dankelmann, Peter; Foucaud, Florent; Henning, Michael A .; María, Arnaud; Parreau, Aline (2018), "Delimitación del orden de una gráfica usando 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), "Dimensión métrica de gráficos de ancho acotado", 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 , 9235 , Springer, págs. 115-126 , doi : 10.1007 / 978-3-662-48054-0_10.
- Blumenthal, LM (1953), Teoría y aplicaciones de la geometría de distancia , Clarendon, Oxford.
- Bonnet, E .; Purohit, N. (2019), "Dimensión métrica parametrizada por el ancho del árbol", en Jansen, BMP; Telle, JA (eds.), Parameterized and Exact Computation 2019 - IPEC 2019: 14th International Symposium, Proceedings , Leibniz International Proceedings in Informatics (LIPIcs), 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 gráficos y la dimensión métrica de un gráfico", Matemáticas aplicadas discretas , 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, Slovenia, 10-12 de septiembre de 2012, Proceedings , Lecture Notes in Computer Science, 7501 , Springer, págs. 419–430, arXiv : 1107.2256 , doi : 10.1007 / 978-3-642-33090-2_37.
- 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 gráficos: 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, Jerusalem, Israel, 26-28 de junio de 2012, Revised Selected Papers , Lecture Notes in Computer Science, 7551 , págs. 114-125, doi : 10.1007 / 978-3-642-34611-8_14.
- Feng, Min; Xu, Min; Wang, Kaishun (2013), "Sobre la dimensión métrica de los gráficos lineales", Matemáticas aplicadas discretas , 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), "Calculando 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 ubicación y dimensión métrica en gráficos de intervalo y permutación. I. Límites", Informática teórica , 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, ubicación-dominación y dimensión métrica en gráficos de intervalo y permutación. 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 NP-Completeness , 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 de doctorado , Technische Universität Berlin , consultado el 15 de septiembre de 2015.
- Hartung, Sepp; Nichterlein, André (2013), "Sobre la dureza parametrizada y aproximada de la dimensión métrica", Conferencia IEEE sobre Complejidad Computacional (CCC) 2013, 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 , S2CID 684505.
- Hauptmann, Mathias; Schmied, Richard; Viehmann, Claus (2012), "Aproximación de la complejidad 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 dimensión métrica y diámetro" , Electronic Journal of Combinatorics , 17 : # R30, doi : 10.37236 / 302.
- Hoffmann, Stefan; Elterman, Alina; Wanke, Egon (2016), "Un algoritmo de tiempo lineal para la dimensión métrica de los gráficos de bloques de cactus", Informática teórica , 630 : 43–62, doi : 10.1016 / j.tcs.2016.03.024
- Hoffmann, Stefan; Wanke, Egon (2012), "La dimensión métrica para los gráficos de disco unitarios de Gabriel es NP-Complete", en 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, Eslovenia, 13-14 de septiembre de 2012, artículos seleccionados revisados , Lecture Notes in Computer Science, 7718 , Springer, págs. 90–92, arXiv : 1306.2187 , doi : 10.1007 / 978-3-642-36092-3_10 , S2CID 9740623.
- Khuller, S .; Raghavachari, B .; Rosenfeld, A. (1996), "Puntos de referencia en gráficos", Matemáticas aplicadas discretas , 70 (3): 217–229, doi : 10.1016 / 0166-218x (95) 00106-2 , hdl : 10338.dmlcz / 140702.
- Lokshtanov, Daniel (2010), "Problemas abiertos - Complejidad parametrizada y algoritmos de aproximación: Dimensión métrica", en Demaine, Erik D .; Hajiaghayi, MohammadTaghi; Marx, Dániel (eds.), Parameterized Complexity and Approximation Algorithms , Dagstuhl Seminar Proceedings, Dagstuhl, Alemania: Schloss Dagstuhl - Leibniz-Zentrum für Informatik.
- Slater, PJ (1975), "Hojas de árboles", Proc. 6ta Conferencia del Sureste sobre Combinatoria, Teoría de Gráficos y Computación (Florida Atlantic Univ., Boca Raton, Fla., 1975) , Congressus Numerantium, 14 , Winnipeg: Utilitas Math., Págs. 549–559, MR 0422062.
- Slater, PJ (1988), "Dominando y conjuntos de referencia en un gráfico", Journal of Mathematical and Physical Sciences , 22 (4): 445–455, MR 0966610.