Premium
On the complexity of the { k }‐packing function problem
Author(s) -
Dobson M. Patricia,
Hinrichsen Erica,
Leoni Valeria
Publication year - 2016
Publication title -
international transactions in operational research
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.032
H-Index - 52
eISSN - 1475-3995
pISSN - 0969-6016
DOI - 10.1111/itor.12276
Subject(s) - chordal graph , combinatorics , mathematics , interval graph , indifference graph , treewidth , vertex (graph theory) , bounded function , discrete mathematics , integer (computer science) , clique sum , split graph , graph , pathwidth , function (biology) , 1 planar graph , computer science , line graph , biology , mathematical analysis , evolutionary biology , programming language
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.