Dominación Romana en Grafos

MARÍA GRACIA CORNET; PABLO TORRES; GABRIELA ARGIROFFO

Rosario

Jornada; XIII Jornada de Ciencia y Tecnología; 2019

Universidad Nacional de Rosario

Enfrentando una reducción en el tamaño del ejército romano por restricciones económicas,el Emperador Constantino (siglo V AC) modificó la estrategia defensiva del Imperio, de lasiguiente forma: las legiones se distribuyen de manera que no haya más de dos legiones encada localidad, toda localidad con al menos una legión puede defenderse de un ataqueexterno sin ayuda y, si una localidad estuviera sin defensa debe haber otra localidadcercana con dos legiones que pueda socorrerla. El problema consiste en encontrar unaasignación de legiones a las distintas localidades del Imperio de manera que cada localidadpueda defenderse (ya sea con o sin ayuda) y minimice la cantidad de legiones. Modelamoseste problema mediante un grafo G=(V,E), donde cada vértice representa una localidad delImperio Romano, y dos vértices están unidos por una arista si las localidadescorrespondientes son vecinas. Consideremos una función f: V → {0,1,2}, de manera quef(v) representa la cantidad de legiones apostadas en la localidad v. Una localidad v seconsidera insegura si no hay ninguna legión apostada allí (es decir, si f(v)=0), y segura encaso contrario (es decir, si f(v)≠0). Consideramos V i el conjunto de vértices v tales quef(v)=i. Diremos que un vértice en V 0 está indefenso con respecto a f, si no es adyacente aningún vértice en V 2 . Y diremos que f no tiene vértices indefensos, si ningún vértice de V 0está indefenso con respecto a f. La función f es una función de dominación romana (RDF)si f no tiene vértices indefensos. El peso de f es la suma ∑{f(v), v∈V}, es decir la cantidadtotal de legiones asignadas por la función f en todo el grafo. Definimos el número dedominación romana, denotado por γ R (G), como el mínimo peso entre todas las RDF; y unafunción donde se realiza este mínimo, es decir, de peso γ R (G), se dice una γ R -función. Elproblema de dominación romana es una variante del problema de dominación clásico. Lagran variedad de aplicaciones prácticas que las variaciones del problema de dominaciónmodelan impulsa al estudio estructural de cada una de ellas, con el objetivo de utilizar estainformación en el análisis de la complejidad computacional de los problemas de decisiónasociados a cada uno de ellos. Estos problemas son NP-completos desde el punto de vistade la complejidad computacional. Sin embargo, el enfoque en términos de grafos ha sidode gran importancia para su estudio y ha contribuido al diseño y mejora de algoritmosespecíficos de resolución. Con esta motivación, estudiamos la relación entre los parámetrosγ(G) y γ R (G), así como la complejidad del problema de dominación romana para ciertasfamilias de grafos para los cuales se conoce su descomposición en subgrafos modulares,como por ejemplo los grafos con pocos P 4 ?s: cografos, P 4 -reducible, P 4 -sparse, P 4 -laden,entre otros.