A set \(D \subseteq V\) of vertices of a graph \(G=(V,E)\) is called a dominating set of G if for every vertex \(u \in V\setminus D\) , there exists a vertex \( v \in D\) such that \( uv \in E(G)\) . A dominating set D is called a bipartite dominating set if G[D], the subgraph induced by D, is bipartite. The domination number of G is the minimum cardinality among all dominating sets of G and it is denoted by \( \gamma (G)\) . The bipartite domination number of G is the minimum cardinality among all bipartite dominating sets of G and it is denoted by \( \gamma _{bip}(G)\) . The Min Dom problem is to find a dominating set of minimum cardinality of a given graph G and Decide Dom is the decision version of the Min Dom problem. Similarly, the Min Bip-Dom problem is to find a bipartite dominating set of minimum cardinality of a given graph G and Decide Bip-Dom is the decision version of the Min Bip-Dom problem. In this paper, we initiate the algorithmic study of the Min Bip-Dom problem. First, we study the complexity difference between the Min Dom problem and the Min Bip-Dom problem. The difference between \(\gamma _{bip}(G)\) and \(\gamma (G)\) of a graph G can be arbitrarily large. However, the Decide Bip-Dom problem is the same as the Decide Dom problem for bipartite graphs and hence is NP-complete for bipartite graphs, as Decide Dom problem is known to be NP-complete for bipartite graphs. We show that Decide Bip-Dom is NP-complete for non-bipartite graphs as well. Finally, we propose polynomial-time algorithms for the Min Bip-Dom problem for interval graphs and block graphs.