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.
ISCO