Sesión Matemática Discreta y Teoría de JuegosFunciones de empaquetamiento flexibles en grafos
María Inés Lopez Pujato
Universidad Nacional de Rosario (FCEIA), Argentina - Esta dirección de correo electrónico está siendo protegida contra los robots de spam. Necesita tener JavaScript habilitado para poder verlo.
Las funciones de empaquetamiento en grafos se utilizan para modelar problemas de asignación de recursos en los que debe ubicarse, en ciertos lugares dados, la mayor cantidad posible de elementos, los cuales son necesarios pero a la vez perjudiciales o indeseados. En [1] se presenta la siguiente definición general de este tipo de funciones: dado un grafo \(G=(V,E)\), un vector de capacidades \(\textbf{k}=(k_v)_{v\in V}\) y vectores \(\textbf{l}=(l_v)_{v\in V}\) y \(\textbf{u}=(u_v)_{v\in V}\) con \(\textbf{l}\leqslant \textbf{u}\) de componentes enteras no negativas, una función \(f:V\to\mathbb{Z}_0^+\) es una función de \((\textbf{k},\textbf{l},\textbf{u})\)-empaquetamiento de \(G\) si \(l_v\leqslant f(v)\leqslant u_v\) y \(f(N[v])\leqslant k_v\) para todo \(v\in V\). El peso de \(f\) es \(f(V)=\sum_{v\in V} f(v)\).
En esta comunicación abordamos el estudio de una variante “flexibilizada” de estas funciones, motivada por ejemplo por el diseño de redes inalámbricas, en el cual los nodos activos no deben tener demasiados vecinos transmitiendo simultáneamente para evitar colisiones. Si en este tipo de situaciones se permite la existencia de nodos inactivos, estos nodos no sufren interferencias, lo que permite a sus vecinos activos transmitir a mayor densidad, aumentando así el rendimiento total del sistema. Esta variante se define de la siguiente manera: dado un grafo \(G=(V,E)\), un vector de capacidades \(\textbf{k}\) y vectores \(\textbf{l}=(l_v)_{v\in V}\) y \(\textbf{u}=(u_v)_{v\in V}\) con \(\textbf{l}\leqslant \textbf{u}\), una función \(f:V\to\mathbb{Z}_0^+\) es una función de \((\textbf{k},\textbf{l},\textbf{u})\)-empaquetamiento flexible si \(l_v\leqslant f(v)\leqslant u_v\) para todo \(v\in V\), y \(f(N[v])\leqslant k_v\) si \(v\) es tal que \(f(v)=u_v\). El número de \((\textbf{k},\textbf{l},\textbf{u})\)-empaquetamiento flexible, \(\textbf{L}^{R}_{\textbf{k},\textbf{l},\textbf{u}}(G)\), es el máximo peso sobre todas las funciones de este tipo, cuando existe al menos una.
Esta flexibilización generaliza nociones clásicas: las funciones de \((\textbf{1},\textbf{0},\textbf{1})\)-empaquetamiento flexible se identifican exactamente con los conjuntos estables, resultando \(\textbf{L}^{R}_{\textbf{1},\textbf{0},\textbf{1}}(G)=\alpha(G)\); y, para \(\textbf{k}=k\cdot \textbf{1}\), las funciones de \((\textbf{k},\textbf{0},\textbf{1})\)-empaquetamiento flexibles se corresponden con los \((k-1)\)-conjuntos dependientes [2].
Estudiamos el problema de decisión asociado (RPP), que consiste en decidir, dados \(G,\textbf{k},\textbf{l},\textbf{u}\) y un entero \(z\), si \(G\) admite una función de \((\textbf{k},\textbf{l},\textbf{u})\)-empaquetamiento flexible de peso al menos \(z\). En particular, establecemos que no se pierde generalidad si solo se consideran cotas inferiores nulas (\(\textbf{l}=\textbf{0}\)) y, por otra parte, de [2] y la conocida \(NP\)-completitud del Problema de Conjunto Estable, derivamos varios resultados de complejidad computacional asociados a RPP. También presentamos un modelo de Programación Lineal Entera con \(n=|V|\) variables y a lo sumo \(3n\) desigualdades, es decir, polinomial en el tamaño de la instancia. Para una instancia \(G\), \(\textbf{k}\) y \(\textbf{u}\) de RPP dada, y llamando \(P(G,\textbf{k},\textbf{u})\) a la cápsula convexa de los puntos factibles del modelo, determinamos la dimensión de este poliedro. Para \(\textbf{u}=\textbf{1}\), caracterizamos cuándo la desigualdad de vecindad asociada a un vértice \(v\) (una de las desigualdades del modelo) define una faceta de \(P(G,\textbf{k},\textbf{1})\) en los casos \(k_v=1\) y \(\textbf{k}=2\cdot\textbf{1}\), y comparamos la relajación resultante con la relajación por aristas del politopo de conjuntos estables de \(G\).
Trabajo en conjunto con: Pablo Fekete (Universidad Nacional de Rosario, Argentina), Erica Hinrichsen (Universidad Nacional de Rosario, Argentina) y Valeria Leoni (Universidad Nacional de Rosario, CONICET, Argentina).
Referencias
[1] E. Hinrichsen, G. Nasini, N. Vansteenkiste, "On general packing functions in graphs", Procedia Computer Science 223 (2023) 367--369.
[2] A. Dessmark, K. Jansen, A. Lingas, "The maximum k-dependent and f-dependent set problem", Algorithms and Computation (ISAAC 1993), Lecture Notes in Computer Science, vol. 762, Springer, Berlín, Heidelberg (1993).