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

M.P. DOBSON; E. HINRICHSEN; LEONI, V.

INTERNATIONAL TRANSACTIONS IN OPERATIONAL RESEARCH

Wiley

Año: 2017 vol. 24 p. 347 - 354

0969-6016

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$. It is known that ${k}$PF is linear time solvable in strongly chordal graphs and in graphs with clique-width bounded by a constant. Nevertheless, up to now the complexity of ${k}$PF for a general graph is not known. In this paper we prove that ${k}$PF is NP-complete, even when restricted to chordal graphs which constitute a superclass of strongly chordal graphs.Looking for 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.