Resumen - Problemas de coloreo de bordes con patrones prohibidos y colores plantados

Problemas de coloreo de bordes con patrones prohibidos y colores plantados

2025-07-25 06:59:35

{"Alexey Barsukov","Antoine Mottet","Davide Perinti"}

{cs.CC,cs.DM}

Este documento investiga problemas de coloración de bordes con patrones prohibidos y colores plantados, enfocándose en la complejidad e inexpressibilidad de estos problemas. Los autores definen los problemas de coloración de bordes con patrones prohibidos como aquellos en los que el objetivo es determinar si los bordes de un grafo pueden colorearse de manera que se eviten ciertas "obstrucciones". Estas obstrucciones están definidas por un conjunto de grafos de bordes coloreados, y el desafío es encontrar una coloración que no permita que ninguna de estas obstrucciones se represente en el grafo coloreado. El documento realiza varias contribuciones clave: 1. **Equivalencia entre problemas de coloración y de extensión**: Para ciertos conjuntos de obstrucciones, los autores muestran que existe una equivalencia polinómica entre el problema de coloración (Col(F)) y el problema de extensión (Ext(F)), donde Ext(F) implica extender una coloración parcial dada para evitar las obstrucciones. 2. **Dichotomía de complejidad**: Para conjuntos naturales de obstrucciones, los autores establecen una dicotomía de complejidad para los problemas de coloración de bordes, lo que significa que tales problemas son o bien en P (resueltos en tiempo polinómico) o NP-completos. 3. **Resultados de inexpressibilidad**: Los autores investigan la relación entre las lógicas MMSNP y GMSNP, que describen ciertas clases de problemas de coloración. Prueban que existen familias de estructuras de bordes coloreados para las que Col(F) no es igual a Col(G) para ninguna familia de estructuras de vértices coloreados, respondiendo una pregunta abierta en el campo. El documento también proporciona varios resultados y construcciones técnicas, incluyendo: - **Determinantes coloreados**: Estos son grafos que ayudan a probar la equivalencia entre Col(F) y Ext(F), y la existencia de tales determinantes para ciertas familias de obstrucciones. - **Dispositivos de igualdad de color**: Estos dispositivos se utilizan para probar la dificultad de ciertos problemas de coloración de bordes. - **Problemas de satisfacción de restricciones infinitos**: Los autores utilizan estos problemas para demostrar la equivalencia entre problemas de coloración de bordes y problemas de satisfacción de restricciones. En resumen, este documento proporciona un análisis exhaustivo y profundo de problemas de coloración de bordes con patrones prohibidos y colores plantados, contribuyendo a nuestra comprensión de la complejidad y la expresividad de estos problemas.