An exact algorithm for connected red–blue dominating set

Abstract

In the Connected Red–Blue Dominating Set problem we are given a graph G whose vertex set is partitioned into two parts R and B (red and blue vertices), and we are asked to find a connected subgraph induced by a subset S of B such that each red vertex of G is adjacent to some vertex in S . The problem can be solved in O⁎(2n−|B|) time by reduction to the Weighted Steiner Tree problem. Combining exhaustive enumeration when |B| is small with the Weighted Steiner Tree approach when |B| is large, solves the problem in O⁎(n1.4143). In this paper we present a first non-trivial exact algorithm whose running time is in O⁎(n1.3645). We use our algorithm to solve the Connected Dominating Set problem in O⁎(n1.8619). This improves the current best known algorithm, which used sophisticated run-time analysis via the measure and conquer technique to solve the problem in O⁎(n1.8966).