On the complexity of the {k}‐packing function problem
María Patricia Dobson, Erica G. Hinrichsen, Valeria Leoni · International Transactions in Operational Research · 2016
Abstract Given a positive integer k, the “ ‐packing function problem” ( 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 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 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 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 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.