On the complexity of the {k}-packing function problem

Given a positive integer k, the ‘{k}‐packing function problem’ ({k}PF) is to find in a given graph G, a function f that assigns a nonnegative integer to the vertices of G in such a way that the sum of f(v) over each closed neighborhood is at most k and over the whole vertex set of G (weight of f) is maximum. It is known that {k}PF is linear time solvable in strongly chordal graphs and in graphs with clique‐width bounded by a constant. In this paper we prove that {k}PF is NP‐complete, even when restricted to chordal graphs that constitute a superclass of strongly chordal graphs. To find other subclasses of chordal graphs where {k}PF is tractable, we prove that it is linear time solvable for doubly chordal graphs, by proving that it is so in the superclass of dually chordal graphs, which are graphs that have a maximum neighborhood ordering.