¿Cuál es la complejidad de este problema de coloración de bordes?

Recientemente, me he encontrado con la siguiente variante de coloración de bordes.

Dado un gráfico conectado no dirigido, encuentre una coloración de los bordes que use la cantidad máxima de colores al tiempo que satisface la restricción de que, para cada vértice , los bordes incidentes a usan como máximo dos colores. $v$ $v$

Mi primera suposición es que el problema es NP-hard. Las pruebas clásicas de NP-hard para problemas de coloración de gráficos son principalmente por reducción de 3SAT. Pero en mi opinión, estas pruebas no son útiles para este problema porque los bordes que inciden en un vértice se pueden colorear con el mismo color, por lo que no podemos construir componentes lógicos en el gráfico.

¿Podría este problema ser NP-hard? En caso afirmativo, ¿qué es una prueba? Si no podemos multar una prueba, ¿hay algún método para determinar la complejidad de este problema?

¡Gracias!

cc.complexity-theory np-hardness complexity-classes graph-colouring RIC_Eien
fuente

¿Quizás la coloración de hipergrafía mixta o limitada por color podría ser un comienzo? Por ejemplo, dx.doi.org/10.1016/j.disc.2008.04.019

András Salamon

Parece que su problema está en P, en dos pasos: (1) su problema es equivalente a encontrar un subconjunto de tamaño máximo de los bordes de modo que cada vértice tenga un grado máximo de dos, y (2) el último problema parece estar en P por, digamos, reducción a la coincidencia. Con respecto a (1), tenga en cuenta que cualquier solución a su problema con k colores le da una subgrafía de grado 2 de tamaño k (solo retenga un borde de cada color), y por el contrario, cualquier subgrafía de grado 2 de tamaño k le da una solución con k colores (solo colorea cada borde en el subgrafo su propio color, colorea el resto de los bordes con cualquiera de los colores). ¿Qué me estoy perdiendo?

Neal Young

Lamento que haya varios errores en su respuesta. Al principio, el problema "encontrar un subconjunto de tamaño máximo de los bordes de modo que cada vértice tenga un grado máximo de dos", es NP-duro, reducción a 3SAT (no sé cómo podría tener una reducción a la coincidencia). Además, "cualquier subgrafo de grado 2 de tamaño k" no da "una solución con k colores", por ejemplo, Gráfico completo. Gracias de todos modos.

RIC_Eien

Sí tienes razón. Aproximadamente (2), el paso "colorear el resto de los bordes con cualquiera de los colores" puede dar algunos bordes de vértice de tres colores. Por separado, Marek Chrobak me sugirió el siguiente algoritmo. Creo que da una aproximación de 3: (i) encontrar una coincidencia máxima M; (ii) colorea cada borde en M su propio color único; (iii) colorea los bordes restantes de blanco.

Neal Young

@RIC_Eien: A riesgo de mayor vergüenza ... ¿Está seguro de que "el problema 'encontrar un subconjunto de tamaño máximo de los bordes de modo que cada vértice tenga un grado máximo de dos', es NP-duro"? Dado G = (V, E), cree G2 bipartito = (U, W, E2), donde para cada vértice v en V hay v 'en U y v' 'en W, y E2 = {(u', w ''): (u, w) en E}. Entonces, las coincidencias en G2 corresponden a los conjuntos de bordes de grado 2 en G, y la correspondencia conserva el tamaño. (Como cada ciclo k C en G corresponde en G2 a un ciclo 2k (si k impar) o dos ciclos k (si k par).) Entonces la coincidencia máxima en G2 lo resuelve. ¿Qué me estoy perdiendo esta vez?

Neal Young

¿Cuál es la complejidad de este problema de coloración de bordes?

Respuestas: