Realizaciones disjuntas de secuencias de grado en grafos con algunas aplicaciones a tomografía discreta

Abstract

Esta tesis trata sobre un problema de reconstrucción en Tomografía Discreta en el cual se está interesado en colorear una grilla usando k colores, de tal forma que para cada fila y columna, el número de celdas de cada color sea un cierto valor previamente dado. Para k = 2, un resultado clásico de la Combinatoria entrega una condición necesaria y suficiente para la existencia de tal coloración junto con un algoritmo polinomial para construirla cuando existe. Por otro lado, Chrobak y Dürr mostraron que para k mayor o igual a 4 el problema es NP-difícil.

La equivalencia natural entre una grilla y un grafo bipartito completo muestra que el caso k=3 corresponde a la restricción a esta clase de grafos del siguiente problema:

Dados un grafo G y funciones enteras b¹ y b² en V(G), ¿existen b¹ y b²-factores de G que sean disjuntos?

En esta tesis introducimos una nueva condición para este problema, la que resulta ser suficiente cuando G es un grafo bipartito completo y la diferencia entre el máximo y mínimo valor de b¹ + b² es a los más dos. La demostración de este resultado se basa en un algoritmo polinomial que encuentra dos factores disjuntos o bien un certificado de inexistencia.

Junto con esto, la contribución principal de esta tesis es la prueba de NP-dificultad del problema para grafos bipartitos completos cuando no se impone ninguna condición a b¹ y b². Esto resuelve el caso k = 3 del mencionado problema en Tomografía Discreta, lo que cierra el problema para todos los valores de k. Como corolario obtenemos además que el problema para grafos completos es también NP-difícil.

Para el problema de unicidad, caracterizamos las transformaciones que preservan las funciones b¹ y b² cuando G es un grafo bipartito. Este resultado es luego utilizado para probar la existencia de invariantes para algunas 3-coloraciones de la grilla.

Además, estudiamos la generalización del problema de k-coloración a la reconstrucción de embaldosados de la grilla usando como baldosas k rectángulos de diferentes tamaños. Para este problema, presentamos demostraciones que abarcan y extienden todos los resultados previos conocidos.

Para finalizar, se prueba la existencia de un núcleo cuadrático para una generalización del problema de Vertex Cover parametrizado por el tamaño requerido del conjunto solución.