Finding a dominating set on bipartite graphs

Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O* (2(n-z)), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O*(2(n/2)). Another implication is an algorithm for general graphs whose running time is O(1.7088(n)). (C) 2008 Elsevier B.V. All rights reserved.