Graph automorphism es una permutación de nodos de gráfico que induce una biyección en el conjunto de aristas . Formalmente, es una permutación de nodos como iff
Defina un borde violado para alguna permutación como un borde que se asigna a no borde o un borde cuya preimagen es no borde.
Entrada : un gráfico no rígido
Problema : encuentre una permutación (sin identidad) que minimice el número de bordes violados.
¿Cuál es la complejidad de encontrar una permutación (sin identidad) con un número mínimo de bordes violados? ¿Es difícil el problema para gráficos con un grado máximo acotado (bajo un supuesto de complejidad)? Por ejemplo, ¿es difícil para los gráficos cúbicos?
Motivación: El problema es una relajación del problema del automorfismo gráfico (GA). El gráfico de entrada puede tener automorfismo no trivial (por ejemplo, gráfico no rígido). ¿Qué tan difícil es encontrar un automorfismo aproximado (permutación de armario)?
Editar 22 de abril
Un gráfico rígido (asimétrico) solo tiene automorfismo trivial. Un gráfico no rígido tiene cierta simetría (limitada) y me gustaría entender la complejidad de aproximar su simetría.
fuente
Respuestas:
La métrica de complejidad es el número de sondas a las matrices de adyacencia, y el objetivo es distinguir los dos casos con alta probabilidad utilizando un número sublineal de sondas.
Eldar Fischer y Arie Matsliah ( gracias, arnab ) tienen un artículo en SODA 2006 sobre precisamente este problema. Si bien no se conecta directamente con su problema, puede ser una forma de formular un posible problema, e incluso podría proporcionarle técnicas útiles.
fuente
Un resultado de Eugene Luks ("El isomorfismo de los gráficos de valencia limitada se puede probar en tiempo polinomial ") muestra que el isomorfismo gráfico (o automorfismo) para gráficos de grado limitado está en tiempo polinomial. Por lo tanto, si está buscando algo (no identidad, como señaló Jukka) de casi automorfismo para gráficos cúbicos que no son rígidos, entonces podemos usar el algoritmo de Luks y tomar cualquier automorfismo no trivial en el gráfico.
fuente