Bipartite-Based 2-Approximation for Dominating Sets in General Graphs

The Dominating Set problem, a fundamental challenge in graph theory and combinatorial optimization, seeks a subset of vertices such that every vertex in a graph is either in the subset or adjacent to a vertex in it. This paper introduces a novel 2-approximation algorithm for computing a dominating set in general undirected graphs, leveraging a bipartite graph transformation. Our approach first handles isolated nodes by including them in the solution set. For the remaining graph, we construct a bipartite graph by duplicating each vertex into two nodes and defining edges to reflect the original graph's adjacency. A greedy algorithm then computes a dominating set in this bipartite graph, selecting vertices that maximize the coverage of undominated nodes. The resulting set is mapped back to the original graph, ensuring all vertices are dominated. We prove the algorithm's correctness by demonstrating that the output set is a valid dominating set and achieve a 2-approximation ratio by adapting a charging scheme to our bipartite construction. Specifically, we show that each vertex in an optimal dominating set is associated with at most two vertices in our solution, guaranteeing the size bound. This method extends the applicability of approximation techniques to general graphs, offering a practical and theoretically sound solution for applications in network design, resource allocation, and social network analysis, where efficient domination is critical.