Defensive Domination in Proper Interval Graphs
share
k-defensive domination, a variant of the classical domination problem on graphs, seeks a minimum cardinality vertex set providing a surjective defense against any attack on vertices of cardinality bounded by a parameter k. The problem has been shown to be NP-complete for fixed k; if k is part of the input, the problem is not even in NP. We present efficient algorithms solving this problem on proper interval graphs with k part of the input. The algorithms take advantage of the linear orderings of the end points of the intervals associated with vertices to realize a greedy approach to solution. The first algorithm is based on the interval model and has complexity O(n · k) for a graph on n vertices. The second one is an improvement of the first and employs bubble representations of proper interval graph to realize an improved complexity of O(n+ | B|·log k) for a graph represented by | B| bubbles.
READ FULL TEXT