Algoritmo de refinamiento del color

En teoría de grafos y ciencias de la computación teórica , el algoritmo de refinamiento de color , también conocido como clasificación de vértices ingenua o versión unidimensional del algoritmo Weisfeiler-Leman , es una rutina utilizada para probar si dos grafos son isomorfos . ^[1] Si bien resuelve el isomorfismo de grafos en casi todos los grafos, hay grafos, como todos los grafos regulares, que no se pueden distinguir mediante el refinamiento de color.

Descripción

El algoritmo toma como entrada un grafo con vértices. Continúa iterando y en cada iteración produce una nueva coloración de los vértices. Formalmente, una " coloración " es una función de los vértices de este grafo en un conjunto (de "colores"). En cada iteración, definimos una secuencia de coloraciones de vértices de la siguiente manera: ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle \lambda _{i}}$

• ${\displaystyle \lambda _{0}}$es la coloración inicial. Si el gráfico no está etiquetado, la coloración inicial asigna un color trivial a cada vértice . Si el gráfico está etiquetado, es la etiqueta del vértice . ${\displaystyle \lambda _{0}(v)}$ ${\displaystyle v}$ ${\displaystyle \lambda _{0}}$ ${\displaystyle v}$
• Para todos los vértices , establecemos . ${\displaystyle v}$ ${\displaystyle \lambda _{i+1}=\left(\lambda _{i}(v),\{\{\lambda _{i}(w)\mid w{\text{ is a neighbor of }}v\}\}\right)}$

En otras palabras, el nuevo color del vértice es el par formado a partir del color anterior y el multiconjunto de los colores de sus vecinos. Este algoritmo va refinando la coloración actual. En algún momento se estabiliza, es decir, . Esta coloración final se denomina coloración estable . ${\displaystyle v}$ ${\displaystyle \lambda _{i+1}\equiv \lambda _{i}}$

Isomorfismo de gráficos

El refinamiento del color se puede utilizar como una subrutina para un importante problema computacional: el isomorfismo de grafos . En este problema tenemos como entrada dos grafos y nuestra tarea es determinar si son isomorfos . De manera informal, esto significa que los dos grafos son iguales hasta que se vuelvan a etiquetar los vértices. ${\displaystyle G,H}$

Para comprobar si y son isomorfos, podemos intentar lo siguiente: ejecutar el refinamiento de color en ambos gráficos. Si las coloraciones estables producidas son diferentes, sabemos que los dos gráficos no son isomorfos. Sin embargo, podría ser que se produzca la misma coloración estable a pesar de que los dos gráficos no sean isomorfos; consulte a continuación. ${\displaystyle G}$ ${\displaystyle H}$

Complejidad

Es fácil ver que si se da como entrada un gráfico de vértices para el refinamiento del color, se produce una coloración estable después de, como máximo, iteraciones. Por el contrario, existen gráficos en los que se cumple este límite. ^[2] Esto conduce a una implementación donde es el número de vértices y el número de aristas. ^[3] Se ha demostrado que esta complejidad es óptima bajo supuestos razonables. ^[4] ${\displaystyle n}$ ${\displaystyle n-1}$ ${\displaystyle O((n+m)\log n)}$ ${\displaystyle n}$ ${\displaystyle m}$

Expresividad

Decimos que dos gráficos y se distinguen por el refinamiento de color si el algoritmo produce una salida diferente en que en . Hay ejemplos simples de gráficos que no se distinguen por el refinamiento de color. Por ejemplo, no distingue un ciclo de longitud 6 de un par de triángulos (ejemplo V.1 en ^[5] ). A pesar de esto, el algoritmo es muy poderoso en el sentido de que un gráfico aleatorio será identificado por el algoritmo de manera asintótica casi con seguridad. ^[6] Aún más fuerte, se ha demostrado que a medida que aumenta, la proporción de gráficos que no se identifican por el refinamiento de color disminuye exponencialmente en orden . ^[7] ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle G}$ ${\displaystyle H}$ ${\displaystyle n}$ ${\displaystyle n}$

La expresividad del refinamiento del color también tiene una caracterización lógica: dos gráficos pueden distinguirse por refinamiento del color si y sólo si pueden distinguirse por el fragmento de dos variables de la lógica de primer orden con conteo . ^[8]

Historia

Referencias

1. Grohe, Martin; Kersting, Kristian; Mladenov, Martin; Schweitzer, Pascal (2021). "Refinamiento del color y sus aplicaciones". Introducción a la inferencia probabilística elevada . doi :10.7551/mitpress/10548.003.0023. ISBN 9780262365598.S2CID 59069015  .
2. Kiefer, Sandra; McKay, Brendan D. (20 de mayo de 2020), El número de iteración del refinamiento del color , arXiv : 2005.10182
3. Cardon, A.; Crochemore, M. (1982-07-01). "Particionado de un grafo en O(¦A¦log2¦V¦)". Ciencias Informáticas Teóricas . 19 (1): 85–98. doi : 10.1016/0304-3975(82)90016-0 . ISSN  0304-3975.
4. Berkholz, Christoph; Bonsma, Paul; Grohe, Martin (1 de mayo de 2017). "Límites inferiores y superiores estrictos para la complejidad del refinamiento de color canónico". Teoría de sistemas informáticos . 60 (4): 581–614. arXiv : 1509.08251 . doi : 10.1007/s00224-016-9686-0 . ISSN  1433-0490. S2CID  12616856.
5. Grohe, Martin (29 de junio de 2021). "La lógica de las redes neuronales de grafos". 2021 36.º Simposio anual ACM/IEEE sobre lógica en informática (LICS) . LICS '21. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 1–17. arXiv : 2104.14624 . doi :10.1109/LICS52264.2021.9470677. ISBN 978-1-6654-4895-6.S2CID233476550  .​
6. Babai, László; Erdo˝s, Paul; Selkow, Stanley M. (agosto de 1980). "Isomorfismo de grafos aleatorios". Revista SIAM de Computación . 9 (3): 628–635. doi :10.1137/0209047. ISSN  0097-5397.
7. Babai, L.; Kucera, K. (1979). "Etiquetado canónico de grafos en tiempo promedio lineal". 20.º Simposio Anual sobre Fundamentos de la Ciencia de la Computación (SFCS 1979) . págs. 39–46. doi :10.1109/SFCS.1979.8 . Consultado el 18 de enero de 2024 .
8. Grohe, Martin. "Lógicas de variables finitas en la teoría de la complejidad descriptiva". Boletín de lógica simbólica 4.4 (1998): 345-398.