Análisis y estudio de complejidad del problema de fragmentación de grafos

Abstract

El objeto de estudio de esta tesis es un problema de optimización combinatoria denominado Problema de Fragmentación de Grafos (GFP). Inspirado por el modelado de epidemias su aplicación puede extenderse a otras clases de desastres, por ejemplo, catástrofes naturales. En esta tesis se estudia el Problema de Fragmentación de Grafos desde el punto de vista de sus propiedades teóricas. El sistema que será afectado se modela como una red, donde un nodo expuesto al desastre inmediatamente lo propaga a sus vecinos. El objetivo del GFP es elegir una estrategia de inmunización de forma en que se minimice el número esperado de muertes causadas. Se presenta el problema mostrando además su relación con el modelo de epidemias clásico SIR y con otro problema teórico de grafos denominado Component Order Connectivity problem. Se prueba que el problema de decisión asociado al GFP pertenece a la clase de problemas N P-completos y también un resultado fuerte de inaproximabilidad que muestra que no existe un algoritmo aproximado de tiempo polinomial para la resolución del GFP con factor menor a 53 , a menos queP =N P. Por último en contraste con el anterior resultado de inaproximabilidad se hallan estrategias de tiempo polinomial para la mejor inmunización en algunas familias especiales de grafos, a saber, ciclos, grafos acíclicos y grafos bipartitos.