Dominación Romana en Grafos

CORNET, MARÍA GRACIA; ARGIROFFO, GABRIELA RUT; TORRES, PABLO

Congreso; LXIX Reunión de Comunicaciones Científicas de la Reunión Anual Virtual de la Unión Matemática Argentina; 2020

Unión Matemática Argentina

Enfrentando una reducción en el tamaño del ejército romano por restricciones económicas, el Emperador Constantino (siglo V a.c.) modificó la estrategia defensiva del Imperio, de la siguiente forma: las legiones se distribuyen de manera que no haya más de dos legiones en cada localidad, toda localidad con al menos una legión puede defenderse de un ataque externo sin ayuda y, si una localidad estuviera sin defensa debe haber otra localidad cercana con dos legiones que pueda socorrerla. El problema consiste en encontrar una asignación de legiones a las distintas localidades del Imperio de manera que cada localidad pueda defenderse (ya sea con o sin ayuda) y minimice la cantidad de legiones.Este problema se modela mediante un grafo G=(V,E), donde cada vértice representa una localidad del Imperio Romano, y dos vértices están unidos por una arista si las localidades correspondientes son vecinas. Consideremos una función f:V-->{0,1,2\}, de manera que f(v) representa la cantidad de legiones apostadas en la localidad v. Una localidad v se considera insegura si no hay ninguna legión apostada allí (es decir, si f(v)=0), y segura en caso contrario (es decir, si f(v)\neq 0). Consideramos V_i el conjunto de vértices v tales que f(v)=i. Diremos que un vértice en V_0 está indefenso con respecto a f, si no es adyacente a ningún vértice en V_2. Y diremos que f no tiene vértices indefensos, si ningún vértice de V_0 está 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 de f(v) sobre V, es decir la cantidad total de legiones asignadas por la función f en todo el grafo. Definimos el número de dominación romana como el mínimo peso entre todas las RDF.El problema de dominación romana es una variante del problema de dominación clásico y consiste en hallar el número de dominación romana para un grafo dado G. Desde el punto de vista de la complejidad computacional este problema es NP-difícil, aún en grafos cordales y grafos bipartitos. Además, este problema puede resolverse en tiempo polinomial para grafos con clique-width acotado por una constante y existen algoritmos lineales que resuelven el problema para cografos y grafos de intervalos.En este trabajo, realizamos un estudio estructural de este problema, con el objetivo de utilizar esta información en el análisis de su complejidad computacional. Estudiamos la relación entre los parámetros de dominación y de dominación romana, así como también analizamos el problema bajo las operaciones de join y unión disjunta de grafos. Este análisis, junto con el cálculo del parámetro en grafos modulares, deriva en un algoritmo lineal para el problema de dominación romana en algunas de las familias de grafos conocidas como grafos con pocos P_4's, como lo son los grafos P_4-sparse, P_4-tidy y P_4-laden entre otras.