Labelled packing functions in graphs

MARTIN SAFE; LEONI, V.; E. HINRICHSEN

INFORMATION PROCESSING LETTERS

ELSEVIER SCIENCE BV

Lugar: Amsterdam; Año: 2020 vol. 154

0020-0190

Given a positive integer $k$ and a graph $G$, a emph{$k$-limited packing} in $G$ is a subset $B$ of its vertex set such that each closed vertex neighborhood of $G$ has at most $k$ vertices of $B$ (Gallant et al., 2010). A first generalization of this concept deals with a subset of vertices that cannot be in the set $B$ and also, the number $k$ is not a constant but it depends on the vertex neighborhood (Dobson et al., 2010).As another variation, a emph{${k}$-packing function} $f$ of $G$ assigns a non-negative integer to the vertices of $G$ in such a way that the sum of the values of $f$ over each closedvertex neighborhood is at most $k$ (Hinrichsen et al., 2014).The three associated decision problems are NP-complete in the general case.We introduce emph{$L$-packing functions} as a unified notion that generalizes all limited packing concepts introduced up to now.We present a linear time algorithm that solves the problem of finding the maximum weight of an $L$-packing function in strongly chordal graphs when a strong elimination ordering is given that includes the linear algorithm for ${k}$-packing functions in strongly chordal graphs (2014). Besides, we show how the algorithm can be used to solve the known clique-independence problem on strongly chordal graphs in linear time (G. Chang et al., 1993).