Bottleneck independent domination on some classes of graphs

Abstract

Let G(V, E, W) be a graph with vertex-set V and edge-set E, and each vertex v is associated with a positive cost W(v). The bottleneck cost of any subset V′ of V is defined to be max{W(x)x ∈ V′}. This paper resolves the Bottleneck Independent Dominating Set problem (the BIDS problem) which determines an independent dominating set of G with the minimum bottleneck cost. The BIDS problem has been proven to be NP-hard on general bipartite graphs. This paper major discusses the problem on two hierarchies of graphs: chordal graphs and bipartite graphs. It first proves that the problem is NP-hard on chordal graphs, but linear-time solvable on weighted split graphs by the greedy approach. Second, it shows that the problem is still NP-hard on planar-bipartite graphs and a linear-time algorithm on weighted convex-bipartite graph is proposed. Finally, an O(n) time algorithm of the BIDS problem on weighted cographs is designed. The later linear-time algorithms are designed by the dynamic programming strategy.