Efficient algorithms for graph isomorphism testing
José Luis López Presa · Dialnet (Universidad de la Rioja) · 2009
: El problema del isomorfismo de grafos ha sido estudiado por los cientificos durante mucho tiempo, desde distintos puntos de vista. Es interesante desde el punto de vista teorico, puesto que no se sabe si es NP-copleto o no. Dado que hay multitud de problemas que pueden reducirse al isomorfismo de grafos, establecer completamente su complejidad, permitiria extrapolar el resultado a todos los problemas que pueden reducirse a el. Ademas, tiene mucho interes practico por las aplicaciones que tiene en campos tan diversos como quimica, vision artificial o mineria de datos. Los algoritmos practicos para el isomorfismo de grafos suelen, o bien tratar de encontrar el isomorfismo mediante un algoritmo clasico de vuelta atras ayudado por una poda heuristica, enfoque que tiene problemas cuando los grafos tienen muchas simetrias (automorfismos), o bien calculado un etiquetado canonico de los vertices, para lo que es necesario calcualr el grupo de automorfismo completo de los grafos, lo que puede resultar mucho mas duro que encontrar el isomorfismo entre ellos. El objetivo de la tesis es disenar y programar un algoritmo para determinar el isomorfismo de grafos, que sea rapido en la practica, que tenga un comportamiento uniforme, y que no necesite para ello calcular completamente el grupo de automorfismo de los grafos. Para evaluar el rendimiento practico de nuestro algoritmo, lo hemos codificado en C y lo hemos comparado con otros dos algoritmos. De una parte vf2, como ejemplo de algoritmo heuristico, que para ciertas familias de grafos tiene un comportamiento muy bueno, y nauty, que el el prpograma de isomorfismo de grafos por excelencia, que usa el otro enfoque y es hoy por hoy el referente mundial, aunque es conocido que tiene un comportamiento exponencial para ciertas familias de grafos. Hoy en dia hay algunas baterias de pruebas que incluyen diversas familias de grafos, pero que no cubren todos tipos de grafos que queriamos tratar. Por ello, hemos generado una bateria de pruebas con nuevas familias de grafos, tanto para probar casos positivos como negativos de isomorfismo. Nuestro algoritmo trabaja en tres fases. En la primera realiza un analisis de los grafos y genera una estructura de datos (secuencia de particiones) para cada uno de ellos. A continuacion busca automorfismos en los grafos a partir de esta secuencia de particiones, y por ultimo, se toma la secuencia de particiones de uno de los grafos como patron, y se trata de generar una secuencia de particiones equivalente para el otro grafo. Los grafos son isomorfos si y solo si es posible reproducir esta estructura de datos para el otro grafo. Este enfoque es novedoso y, en las pruebas que hemos realizado con nuestra bateria de grafos, hemos comprobado que tiene un comportamiento uniforme con todas las familias de grafos consideradas, y que en algunos casos tiene un rendimiento similar a los otros algoritmos, mientras que en otros los desborda completamente. Los casos mas significativos son aquellos en los que nauty y vf2 tienen un comportamiento exponencial, mientras que nuestro algoritmo conauto tiene un comportamiento polinomico. Este ocurre con una familia de grafos contruida por Takunary Miyazaki a partir de una contruccion de Martin Furer, y con grafos union (por ejemplo, grafos generados mediante la union disjunta de componentes sencillas). Hemos demostrado la correccion de nuestro algoritmo y hemos analizado su complejidad espacial y temporal. Probamos que tiene una complejidad espacial de 0(n2) palabras para grafos de n vertices. En el caso mejor, tiene una complejidad temporal 0(n2), y con alta probabilidad es polinomico.