Towards a polynomial equivalence between {k}-packing functions and k-imited packings in graphs

DOBSON, M.P; LEONI, V.

LECTURE NOTES IN COMPUTER SCIENCE

Springer

Año: 2016 vol. 9849 p. 160 - 165

0302-9743

Given a positive integer $k$, the ${k}$-emph{packing function problem} (${k}$PF) is to find in a given graph $G$, a function $f$ of maximum weight that assigns a non-negative integer to the vertices of $G$ in such a way that the sum of $f(v)$ over each closedneighborhood is at most $k$. This notion was recently introduced as a variation of the $k$-limited packing problem ($k$LP) introduced in 2010, where the function was supposed to assign a value in ${0,1}$. For all the graph classes explored up to now, ${k}$PF and $k$LP have the same computational complexity. It is an open problem to determine a graph class where one of them is NP-complete and the other, polynomially solvable. In this work, we first prove that ${k}$PF is NP-complete for bipartite graphs, as $k$LP is known to be. We also obtain new graph classes where the complexity of these problems would coincide.