Open packing in interval graphs

Total domination and open packing form a primal-dual pair of problems. A vertex subset S of a graph G is called an open packing in G if no pair of distinct vertices in S have a common neighbor in G. The cardinality of a maximum open packing in G is called the open packing number, \(\rho ^o(G)\) ${\rho }^o(G)$ , of G which is a lower bound for the total domination number of G. Given a graph G and a positive integer k, the problem Open Packing tests whether G has an open packing of size at least k. It is known that Open Packing is NP-complete for split graphs (and so for chordal graphs) [1]. In this work, we use a dynamic programming based approach to show that a maximum open packing in interval graphs (a subclass of chordal graphs) can be found in \(O(n^3)\) $O(n^3)$ time.