stringtranslate.com

Dimensión métrica (teoría de grafos)

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. [2]

Propiedades

En Chartrand et al. (2000), se demuestra que:

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. [3] Sigue siendo NP-completo para gráficos planares de grado acotado , [4] gráficos divididos , gráficos bipartitos y sus complementos , gráficos lineales de gráficos bipartitos, [5] gráficos de disco unitario , [6] gráficos de intervalo de diámetro 2 y gráficos de permutación de diámetro 2, [7] y gráficos de ancho de árbol acotado . [8]

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 , [7] y, más generalmente, a grafos de longitud de árbol acotada, [9] 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 , [5] grafos de cadena , [11] y grafos de bloques de cactus [12] (una clase que incluye tanto grafos de cactus como grafos de bloques ). El problema se puede resolver en tiempo polinomial en grafos planos exteriores . [4] También se puede resolver en tiempo polinomial para grafos de número ciclomático acotado , [5] 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 ", [13] "número máximo de hojas", [14] y "ancho modular". [9] 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 . [9]

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 . [15] 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, . [16] 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 . [16] La última dureza de aproximación todavía se mantiene para casos restringidos a gráficos subcúbicos, [13] e incluso a gráficos subcúbicos bipartitos . [17]

Referencias

Notas

  1. ^ 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.
  2. ^ Feng, Xu y Wang 2013.
  3. ^ Garey y Johnson 1979.
  4. ^ ab Díaz et al. 2012.
  5. ^ abc Epstein, Levin y Woeginger 2012.
  6. ^ Hoffmann y Wanke 2013.
  7. ^ desde Foucaud y otros, 2017b.
  8. ^ Li y Pilipczuk 2022.
  9. ^ abc Belmonte y otros 2015.
  10. ^ Más tarde 1975; Harary y Melter 1976.
  11. ^ Fernau y otros 2015.
  12. ^ Hoffmann, Elterman y Wanke 2016.
  13. ^ ab Hartung y Nichterlein 2013.
  14. ^ Eppstein 2015.
  15. ^ Khuller, Raghavachari y Rosenfeld 1996.
  16. ^ ab Hauptmann, Schmied y Viehmann 2012.
  17. ^ Hartung 2014.

Bibliografía