División de bordes en triángulos arcoiris

9

Me pregunto si el siguiente problema es NP-hard.

Entrada: G=(V,E) un gráfico simple y una coloración de los bordes ( no verifica ninguna propiedad específica).ff:E{1,2,3}f

Pregunta: ¿ es posible dividir en triángulos | E | / 3 , de modo que cada triángulo tenga un borde de cada color?| E | / 3E|E|/3

Sé que sin los colores, el problema de "dividir los bordes" de un gráfico en , es NP-hard (ver NP-Completeness of Some Edge-Partition Problems ) pero con los colores que no conozco. n 3Knn3

También me interesaría un resultado para la partición de bordes en el arco iris , con una constante. Por supuesto, en este caso el problema se convierte en: cKcc

Entrada: un gráfico simple y una coloración de los bordes ( no verifica ninguna propiedad específica) .f : E { 1 , , c ( c - 1 ) / 2 } fG=(V,E)f:E{1,,c(c1)/2}f

Pregunta: ¿ es posible dividir en 's, de modo que cada camarilla tenga un borde de cada color?| E | / ( c ( c - 1 ) / 2 ) K c K cE|E|/(c(c1)/2) KcKc

usuario32018
fuente

Respuestas:

1

Seguí el enlace en la pregunta, y la reducción allí en realidad produce gráficos cuyos bordes tienen una coloración natural de modo que cada Kn presente en el gráfico es un "arco iris Kn " (tiene exactamente un borde de cada color). En otras palabras, podemos ajustar fácilmente la reducción en la que el papel de manera que se reduce a su problema en lugar de reducir a la partición en Kn problema s: simplemente asignar a cada borde un color de acuerdo con este colorante natural y entonces la gráfica se puede dividir en "arco iris Kn s" si y solo si podría dividirse en Kn s.

La estructura básica de la reducción en ese papel se puede lograr con los siguientes 3 pasos:

  1. Crear muchas copias de un gráfico particular Hn,p .
  2. Identifique ciertas piezas de algunas copias de Hn,p entre sí (es decir, combine vértices / bordes entre múltiples copias diferentes de Hn,p ).
  3. Eliminar ciertos vértices / bordes de algunas copias.

El gráfico Hn,p tiene como vértices el conjunto de vectores de longitud n módulo p para el cual los componentes se suman a 0 mod p . Los bordes conectan cada dos vértices que difieren en solo dos componentes con diferencias de +1 y 1 en esos dos componentes.

Propongo el siguiente color para este gráfico: asigne un color a cada borde de acuerdo con su dirección. Si x e y son vértices adyacentes, entonces xy es un vector con n2 componentes iguales a 0 , un componente igual a 1 y un componente igual a 1 . En otras palabras, para cada borde (x,y) hay opciones para qué componentes de(n2)xyson distintos de cero Si asignamos un color único a cada una de estas opciones, entonces tenemos un color para todos los bordes, de modo que cada borde en la misma dirección tenga el mismo color. Es bastante fácil verificar que no haya dos aristas en una en en la misma dirección. Por lo tanto, cada en es un arcoíris bajo este color.KnHn,pKnHn,pKn

Cuando seguimos la reducción, usamos este color para cada copia de . Por lo tanto, al final del paso 1 en la lista anterior, cada en el gráfico es un arco iris .Hn,pKnKn

En el paso 2 de la lista anterior, identificamos algunos vértices / aristas entre sí. En particular, en la reducción siempre identificamos una con otra . Pero en esta situación (donde todos los s son de una copia de ), cada es una traducción del " estándar " que el documento llama o una traducción de . Por lo tanto, estamos identificando dos s paralelas o dos s que son "volteretas" entre sí. En cualquier caso, los bordes que se identifican a través de los dosKnKnKnHn,pKnKnKKKnKnKnK n K n K ns son paralelas y, por lo tanto, son del mismo color. Por ejemplo, vea la Figura 2 en el documento; Las aristas identificadas son siempre paralelas. Por lo tanto, dado que nunca intentamos identificar dos bordes de diferentes colores, la coloración al final del paso 1 en la lista anterior se puede extender naturalmente a una coloración al final del paso 2. Identificar ciertos vértices / bordes juntos no crea cualquier s nuevo , por lo que sigue siendo el caso al final de este paso que cada es un arcoíris .KnKnKn

Finalmente, en el paso 3 eliminamos algunos vértices / bordes, que tampoco crean nuevos s. Por lo tanto, tenemos nuestra propiedad deseada: bajo el color que proporcioné, cada en el gráfico generado por esta reducción es un arco iris .KnKnKn

Mikhail Rudoy
fuente