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

Given a positive integer k, the {k}-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 closed neighborhood is at most k. This notion was recently introduced as a variation of the k-limited packing problem (kLP) 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 kLP 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 kLP is known to be. We also obtain new graph classes where the complexity of these problems would coincide. Fil: Leoni, Valeria Alejandra. Consejo Nacional de Investigaciones Científicas y Técnicas. Centro Científico Tecnológico Conicet - Rosario; Argentina. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina Fil: Dobson, Maria Patricia. Universidad Nacional de Rosario. Facultad de Ciencias Exactas Ingeniería y Agrimensura. Escuela de Ciencias Exactas y Naturales. Departamento de Matemática; Argentina