Released packing functions in graphs

Abstract

We introduce and start the study of a variant of packing functions in graphs. Given a graph $G$ with vertex set $V$ and nonnegative integer vectors $\mathbf{k}=(k_v{)}_{v\in V}$, $\mathbf{\ell }=(l_v{)}_{v\in V}$ and $\mathbf{u}=(u_v{)}_{v\in V}$, a function $f:V\to {\mathbb{Z}}_0^{+}$ is a Released $(\mathbf{k},\mathbf{\ell },\mathbf{u})$-packing function of $G$ if $l_v\le f(v)\le u_v$ for every $v\in V$ and the sum of the values of $f$ over the closed neighborhood of vertices $v$ with $f(v)=u_v$ is at most $k_v$. The weight of $f$ is the value $f(V)={\sum }_{v\in V}f(v)$. We study the associated decision problem (RPP), which asks, given $G$, $\mathbf{k}$, $\mathbf{\ell }$, $\mathbf{u}$ and an integer number $x$, whether $G$ admits a Released $(\mathbf{k},\mathbf{\ell },\mathbf{u})$-packing function of weight at least $x$. We relate RPP to the $r$-dependent set problem, derive several NP-hardness results, model RPP as a compact (polynomial in size) Integer Linear Program, and take the first steps of a polyhedral study.

11 pages, 1 fugure