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}$, $\boldsymbol\ell=(l_v)_{v\in V}$ and $\mathbf{u}=(u_v)_{v\in V}$, a function $f : V \rightarrow \mathbb{Z}_0^+$ is a Released $( \mathbf{k}, \boldsymbol\ell, \mathbf{u})$-packing function of $G$ if $l_v\leq f(v)\leq 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}$, $\boldsymbol\ell$, $\mathbf{u}$ and an integer number $x$, whether $G$ admits a Released $( \mathbf{k}, \boldsymbol\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.

Disclosure

“l de Rosario through project 80020190100039UR. 6 Declaration of generative AI and AI-assisted tech- nologies in the manuscript preparation process During the preparation of this work the authors used Google Gemini 3.1 Pro and Claude Sonnet 4.6 in order to improve the readability and language of the manuscript and to help identify typographical errors and inconsistencies in notation. After using this tool/service, the authors reviewed and edited the content as needed and take”

PDF page 10

Classification

Proofreading, grammar, or spelling

Multiplier

1

Verified

2026-08-23T05:10:34.605472Z

Structural counts