El problema de dominación clásico en un grafo G=(V,E) es el problema de hallar un conjunto dominante de cardinal mínimo, es decir, un subconjunto D de V de cardinal mínimo tal que D tenga intersección no vacía con las vecindades cerradas de cada vértice de G o, equivalentemente, hallar una función f de V en {0,1} de peso mínimo y que satisfaga que, para todo i de V, sum_{j in N[i]}f(j)>=1.
Numerosas aplicaciones pueden ser modeladas como problemas de dominación en grafos (ver [H]). La mayoría de estos problemas son NP-difíciles, desde el punto de vista de la complejidad computacional, sin embargo, el enfoque en términos de grafos ha sido de gran importancia para la resolución de problemas del área como así también, contribuido al diseño y mejora de algoritmos específicos de resolución de algunas instancias.
Habitualmente, cada aplicación específica impone restricciones adicionales a los conjuntos dominantes, surgiendo de esta manera diferentes variaciones del problema. En efecto, a partir del concepto de dominación en grafos se modelan entre otros, problemas de locación de servicios. En particular, en este proyecto se abordarán las siguientes variaciones:
- el problema de k-dominación en un grafo: dado k natural, se pretende hallar una función f de V en {0,1} de peso mínimo y tal que para todo i de V, (2) sum_{j in N[i]}f(j)>=k [HH].
- el problema de {k}-dominación en un grafo: dado k natural se pretende hallar una función f de V en {0,1,...,k} de peso mínimo y que satisfaga (2) [BBHS].
- el problema de dominación de Grundy: hallar una secuencia de vértices {v1,v2,...,vr} de cardinal máximo que sea un conjunto dominante y tal que N[vi]-cup_{j- el problema de códigos de identificación: hallar un conjunto dominante D de cardinal mínimo tal que N[i]cap D eq N[j]cap D.
Por otro lado, si A es la matriz cuyas filas son los vectores característicos de las vecindades cerradas de los vértices de G, un vector x de entradas 0,1 (0,1,...,k) corresponde a un conjunto k-dominante (respectivamente {k}-dominante) si Ax >= k. De esta forma, pueden modelarse estos problemas como hallar el mínimo de 1x para x 0-1 (k-dominación) o x entero ({k}-dominación) tal que Ax>=k.
En este sentido, determinar familias de grafos donde las desigualdades lineales que participan en la descripción de la cápsula convexa de las soluciones enteras puedan ser identificadas, es una tarea de gran riqueza tanto desde el punto de vista teórico como desde el punto de vista de la implementación de algoritmos que resuelvan el problema eficientemente.
La tarea de desarrollo de este proyecto se enmarcará en el estudio de los problemas mencionados, haciendo uso de técnicas que proporcionan la teoría de grafos y el enfoque poliedral del problema, herramientas consolidadas en el abordaje de los problemas de Optimización Combinatoria.
