La complejidad de la distribución equitativa de las particiones

Question

Estamos hablando de grafo simple de gráficos y particiones de sus vértices conjuntos disjuntos no vacíos de las células. Dicha partición es equitativo si para cualquier par de vértices $v,w$ en la misma celda, y cualquier celda $C$, sostiene que $v,w$ tienen el mismo número de vecinos,$C$. El trivial de la partición (con sólo un vértice por celda) es siempre equitativo.

Dado cualquier partición $\pi$, no hay una única más tosca partición equitativa $\bar\pi$ más fino que el de $\pi$. (Los conceptos más finos y más gruesos incluir la igualdad). Esta es una muy antigua resultado, como también se polinomio de tiempo de algoritmos para calcular $\bar\pi$ de $\pi$.

Otro hecho es que es NP-completo para determinar si una gráfica tiene una partición equitativa con cada célula de tamaño 2. (Esto se deduce de la Lubiw, SIAM J Comput 10, 1981, 11-21 de señalar que dicha partición corresponde a un punto fijo-libre automorphism de orden 2.)

Mi pregunta es: ¿qué más? De ningún otro tipo, la complejidad de los resultados conocidos? En particular:

1. ¿Cuál es la complejidad de la: Dado un gráfico regular, tiene la no-trivial equitativa partición distinta de la partición con sólo una célula?
2. ¿Cuál es la complejidad de la: Dado un gráfico regular, tiene una partición equitativa con exactamente dos células?
3. ¿Cuál es la complejidad de la: Dado un grafo y dos vértices $v,w$, hay un no-trivial equitativa de la partición que ha $v,w$ en las diferentes células?
4. Hay algún problema en la equidad de particiones con la complejidad igual a la gráfica de isomorfismo?

Answer 1

Aquí es una respuesta parcial a la cuarta pregunta.

La fracción Gráfico Isomorfismo problema (véase el correspondiente papel y el libro) está relacionado con el problema de la informática equitativa de las particiones de un gráfico. La fracción Gráfico no es más que el Gráfico de Isomorfismo problema por lo que parece probable que muchos de los problemas en la equidad de las particiones no será más que el Gráfico de Isomorfismo problema.

Considere la Gráfica Isomorfismo problema como el problema de determinar si existe una matriz de permutación $P$ tal que $AP = PB$ donde $A$ e $B$ son las matrices de adyacencia de los dos gráficos. Este es realmente el problema de la determinación de la viabilidad de un número entero de programación lineal (donde las entradas de $P$ son las variables desconocidas).

La fracción Gráfico Isomorfismo problema es el de la relajación que permite a $P$ a ser doblemente estocástica de la matriz en lugar de una matriz de permutación. Ahora este problema se puede plantear como un problema de programación lineal en lugar de un número entero lineal del programa, así que puede ser resuelto en el polinomio de tiempo. (Se desconoce si el Gráfico de Isomorfismo puede ser resuelto en el polinomio de tiempo, y, más en general, de programación lineal entera no puede ser resuelto en el polinomio tiempo, a menos que $\mathsf{P} = \mathsf{NP}$.)

Según las referencias enlazado más arriba, las fracciones de Gráfico de Isomorfismo es equivalente al problema de determinar si dos gráficos tienen un común más tosca equitativa de la partición, o simplemente cualquier comunes equitativa de la partición.

Answer 2

Más un comentario que una respuesta. Tengo (como lo sugiere) hizo una pregunta relacionada con lo que es esencialmente acerca de la complejidad de la determinación de si un determinado espacio propio, un miembro con dos entradas.

En relación con esta pregunta, aquí es una increíblemente vago esbozo de un posible tipo de enfoque para un intento de construcción de una dificultad potencial de ejemplo para la pregunta 2: Comenzar con un conectada gráfico bipartito $H$, lo que ha $2m$ vértices $v_1 \cdots v_{2m}$ todos de grado $d$ (de modo que las dos mitades de cada uno tiene $m$ vértices) pero por lo demás es bastante irregular. También generar $2m$ gráficos $G_1 \cdots G_{2m}$ cada una con $n$ vértices, regular de grado $d^*$ y todas las $0$ como un valor propio de un nivel razonablemente alto de la multiplicidad, pero sin ninguna muy simple vectores propios. Ahora hacer de ellos un gran gráfico de $\mathcal{G}$ con $2mn$ vértices poniendo en todos los $n^2$ bordes de conectar $G_i$ e $G_j$ siempre $v_iv_j$ es un borde de $H.$ habrá una enorme cantidad de bastante complicado vectores propios de $\mathcal{G}$ obtenido por elegir arbitrariamente el autovector de $0$ para cada una de las $G_i.$ También habrá un autovector que es $1$ en la mitad de los vértices y $-1$ en la otra mitad (respetando el desdoblamiento de $H$.) Ahora bien, si la gráfica es la que acaba de ser presentado como una gran matriz de adyacencia con vértices en un muy revueltos fin de entonces estará claro que $0$ es un eignevalue de alta multiplicidad y nuestro favorito, el programa nos presentará una base para el correspondiente espacio propio, pero puede no ser obvio cómo encontrar a ese ser especial autovector.

La izquierda no especificado es cómo escoger bien los valores de $m,n,d,d^*$ Quizá no es una simple falla en esta descripción, tal vez demasiados fáciles de encontrar $0,1,-1$ vectores propios. En ese caso yo digo que eso fue sólo un boceto. En alguna otra forma de construir de manera equitativa (dos células) de la partición de las cubrió con un montón de ruido.

Answer 3

Para la pregunta 4, es NP-completo para decidir si un bipartito gráfico de $G(V_1 \cup V_2, E)$ tiene un automorphism de orden 2 que el intercambio de las dos clases de color. Si dejamos caer el requisito de orden 2, entonces el problema se convierte en equivalente para la Gráfica de Isomorfismo problema. La correspondencia entre el orden de 2 de punto fijo libre de automorfismos y equitativa particiones debe ayudarle a transferir el último resultado equitativo particiones (tenga en cuenta que el requisito de la alternancia de las dos clases de color fuerzas de la automorphism a ser de punto fijo gratis).

Answer 4

    
Sobre La Pregunta 1, parece que la partición de un hipercubo en dos en diagonal cruzando los conjuntos de es un equipartition: en los dos ejemplos mostrados, cada vértice azul tiene dos vecinos en la púrpura conjunto, y viceversa. Esto continúa a $d$-dimensiones hypercubes, proporcionando un ejemplo de una $d$-gráfico regular con un 2-equipartition.