Sesión Matemática DiscretaEmpaquetamientos generalizados en grafos con clique-width acotado
Natalí Romina Vansteenkiste
Facultad de Ciencias Exactas, Ingeniería y Agrimensura, UNR - CONICET, Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Los empaquetamientos en grafos modelan problemas de ubicación de recursos, como por ejemplo de puntos de venta en un mercado saturado, donde es necesario imponer restricciones de máxima cantidad de unidades a ser ubicadas en un lugar y en su vecindad.
Dado un grafo $G=(V,E)$ y $\mathbf k, \mathbf u\in \mathbb Z_+^V$, un $(\mathbf k, \mathbf u)$-empaquetamiento de $G$ es una función $f:V\rightarrow \mathbb Z_{+}$ que satisface $0\leq f(v)\leq u(v)$ y $f(N[v])\leq k(v)$, para todo $v\in V$. El problema de optimización asociado (PEG) consiste en calcular el valor máximo de $f(V)$ entre todos los $(\mathbf k, \mathbf u)$-empaquetamientos $f$ de $G$. Con respecto al análisis de complejidad computacional, es útil considerar instancias de PEG con capacidades acotadas por una constante, esto es, dado $M\in \mathbb Z_+$, notamos $M$-PEG a PEG reducido a instancias donde $\mathbf \leq M \mathbf{1}$. En la literatura se han estudiado otros problemas de empaquetamiento en grafos [3, 4, 5, 6], todos los cuales pueden ser pensados como el PEG con restricciones sobre $\mathbf k$ y $\mathbf u$ en sus instancias. Entre los resultados de complejidad computacional de estos problemas, en [2] se prueba que en grafos dualmente cordales el PEG es NP-difícil y resulta polinomial cuando se reduce a instancias donde $\mathbf u=\mathbf k= \mathbf 1 k$ , para un $k\in \mathbb Z_+$ fijo, llamadas funciones $\{k\}$-empaquetadoras.
En lo referido a grafos con \emph{clique-width} acotado, a partir del Teorema de Courcelle [1] se prueba la polinomialidad del PEG reducido a instancias donde $\mathbf{u}= \mathbf 1$ y $\mathbf k=k \mathbf 1$ para un $k\in \mathbb Z_+$ fijo (empaquetamientos $k$-limitados). Una reducción polinomial entre los dos problemas permitió tambien demostrar la polinomialidad para el caso de funciones $\{k\}$-empaquetadoras [5]. Con el objetivo de obtener resultados más generales en clases de grafos con clique-width acotado, en [7] se trabaja con el PEG en grafos $P_4$-\emph{tidy} a partir de su descomposición modular. Se presentan fórmulas para resolver el PEG en la unión y join de grafos generales y se inicia el estudio sobre los grafos quasi-arañas. Para instancias con $\textbf{k}\in \mathbb Z_+^V$ y $\textbf{u}\geq \textbf{k}$ se resuelve en grafos arañas flacas y se obtienen resultados parciales para grafos arañas gordas.
En este trabajo se prueba que el $M$-GPF es polinomial en grafos con \emph{clique-width} acotado y se presenta un algoritmo lineal para el GPF en arañas gordas sin cabeza, que deriva en un algoritmo polinomial específico para el PEG en la subclase de grafos $P_4$-\emph{sparce}.
Trabajo en conjunto con: Erica Hinrichsen (Universidad Nacional de Rosario, Argentina) y Graciela Nasini (Universidad Nacional de Rosario, CONICET, Argentina).
Referencias
[1] Courcelle, B., Makowsky J. A., Rotics U.: Linear Time Solvable Optimization Problems on Graphs of Bounded Clique Width. Theory of Computing Systems 33, 125--150, 2000.
[2] Dobson, M. P., Hinrichsen, E., Leoni, V.: On the complexity of the {k}-packing function problem, International Transactions in Operational Research 24, 347–354, 2017.
[3] Dobson M. P., Leoni V., Nasini G.: The k-limited packing and k-tuple domination problems in strongly chordal, P4-tidy and split graphs. Electron. Notes Discrete Math., 36(23-24):559-556, 2010.
[4] Gallant R., Gunther G., Hartnell B. L., Rall D.: Limited packings in graphs. Discrete Appl. Math., 158(12):1357-1364, 2010.
[5] Hinrichsen E. G. Leoni V.: {k}-packing functions of graphs. Lecture Notes in Comput. Sci., 8596:325-335, 2014.
[6] Hinrichsen E. G., Leoni V., Safe M.D.: Labelled packing functions in graphs. Inform. Process. Lett., 154:105863, 7, 2020.
[7] Hinrichsen E., Nasini G., Torres P., Vansteenkiste N.: Problema de empaquetamiento generalizado en grafos con pocos P4's, LXVIII Reunión Anual de Comunicaciones Científicas UMA 2019.