Sesión Matemática Discreta

Diciembre 14, 15:30 ~ 15:50

Funciones $L$-empaquetadoras y un algoritmo para grafos fuertemente cordales

Hinrichsen, Erica

Los empaquetamientos $k$-limitados generalizan a los 2-empaquetamientos en grafos y modelan, entre otros, problemas de locación de servicios en los cuales se requiere que a lo sumo $k$ servicios sean ubicados en las cercanías de cada usuario. Formalmente, dado un $k\in \mathbb Z_+$ y un grafo $G$, un \emph{empaquetamiento $k$-limitado } en $G$ es un subconjunto $B$ de su conjunto $V(G)$ de vértices tal que cada vecindad cerrada tiene a lo sumo $k$ vértices de $B$ [3]. El problema de optimización asociado consiste en encontrar el cardinal máximo entre todos los empaquetamientos $k$-limitados en $G$. Una extensión de este concepto, la de \emph{empaquetamiento generalizado}, tiene en cuenta que determinados vértices tienen prohibido estar en $B$ y que la vecindad cerrada de todo vértice $v$ está acotada por un número dependiente de $v$, $k(v)$ [2]. Para modelizar situaciones en las que se permite ubicar más de un servicio, se define otra variación de los empaquetamientos $k$-limitados. Para un $k\in \mathbb Z_+$ y un grafo $G$, una función $f$ es \emph{ $\{k\}$-empaquetadora} de $G$ si asigna un valor $f(v)\in \mathbb Z_+$ a cada $v\in V(G)$ tal que la suma de los valores de $f$ sobre cada vecindad cerrada es a lo sumo $k$. Se busca el valor máximo $\sum_{v\in V(G)}f(v)$ entre todas las funciones $\{k\}$-empaquetadoras de $G$ [4]. Los problemas de decisión asociados a los de optimización arriba descriptos son NP-difíciles, pero se pueden resolver en tiempo polinomial para grafos fuertemente cordales [1, 2]. En este trabajo damos un enfoque unificador para estos tres problemas: dados $G$ y $k\in \mathbb Z_+$ y una función $L$ sobre $V(G)$, tal que $L(v)=(t(v),k(v))$ con $t(v)\in \{0,\ldots,k\}\cup \{A\}$ y $ k(v)\in \mathbb Z_+$, $f$ es una función \emph{$L$-empaquetadora} de $G$ si asigna un entero no negativo a cada elemento de $V(G)$ y que satisface: si $t(v) \neq A $ entonces $f(v)=t(v)$, y para todo $v\in V(G)$, $f(N_G[v]) \leq k(v)$. Presentamos un algoritmo unicador para grafos fuertemente cordales de tiempo lineal en el tamaño del grafo de entrada. Mostramos una reducción lineal del problema de decisión asociado hacia el del empaquetamiento generalizado, que combinanda con una de las reducciones en [5] concluimos que el problema original del empaquetamiento $k$-limitado es ``tan difícil'' ---desde el punto de vista de su complejidad computacional--- como el introducido en este trabajo, en las clases de grafos que son cerradas a través de las transformaciones involucradas. \begin{thebibliography}{10}\label{bibliography} \bibitem{angeles3} Dobson, M. P., E. Hinrichsen, V. Leoni, ``On the complexity of the $\{k\}$-packing function problem'', International Transactions in Operational Research. 2016, en prensa. \bibitem{ISCODLNpacking} Dobson M. P., V. Leoni, G. Nasini, \emph{The $k$-limited packing and $k$-tuple domination problems in strongly chordal, $P_4$-tidy and split graphs}, Electronic Notes in Discrete Mathematics \textbf {36} (2010), 559--566. \bibitem{GGHR1} Gallant R., G. Gunther, B. Hartnell, D. Rall, \emph{Limited packing in graphs}, Discrete Applied Mathematics \textbf{158} Issue 12 (2010), 1357--1364. \bibitem{HLLNCS2014} Hinrichsen E., V. Leoni, \emph{$\{k\}$-packing functions in graphs}, Lecture Notes in Computer Science, Springer, Heidelberg (2014), 325--335. \bibitem{LNreductions} Leoni V., N. Nasini, \emph{Limited Packing and Multiple Domination problems: Polynomial time reductions}, Discrete Applied Mathematics \textbf{164} (2014) 547--553. \end{thebibliography}

Autores: Hinrichsen, Erica / Safe, Martín / Leoni, Valeria.