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

Frank Vega

Information Physics Institute, 840 W 67th St, Hialeah, FL 33012, USA

[email protected]

Problem Statement

Given an undirected graph


$G=(V,E)$

, the goal is to find a dominating set

$S\subseteq V$

, where a set

$S$

is dominating if every vertex in

$V$

is either in

$S$

or adjacent to a vertex in

$S$

. We aim to design an algorithm that produces a dominating set

$S$

such that

$|S|\le 2\cdot |OPT|$

, where

$OPT$

is the size of a minimum dominating set in

$G$

, thus achieving a 2-approximation.

Algorithm Description

Consider the algorithm implemented in Python:

import networkx as nx



def find_dominating_set(graph):

    """

    Approximate minimum dominating set for an undirected graph by transforming it into a bipartite graph.



    Args:

        graph (nx.Graph): A NetworkX Graph object representing the input graph.



    Returns:

        set: A set of vertex indices representing the approximate minimum dominating set.

             Returns an empty set if the graph is empty or has no edges.

    """

    # Subroutine to compute a dominating set in a bipartite component, used to find a dominating set in the original graph

    def find_dominating_set_via_bipartite_proxy(G):

        # Initialize an empty set to store the dominating set for this bipartite component

        dominating_set = set()

        # Track which vertices in the bipartite graph are dominated

        dominated = {v: False for v in G.nodes()}

        # Sort vertices by degree (ascending) to prioritize low-degree nodes for greedy selection

        undominated = sorted(list(G.nodes()), key=lambda x: len(list(G.neighbors(x))))



        # Continue processing until all vertices are dominated

        while undominated:

            # Pop the next vertex to process (starting with lowest degree)

            v = undominated.pop()

            # Check if the vertex is not yet dominated

            if not dominated[v]:

                # Initialize the best vertex to add as the current vertex

                best_vertex = v

                # Initialize the count of undominated vertices covered by the best vertex

                best_undominated_count = -1



                # Consider the current vertex and its neighbors as candidates

                for neighbor in list(G.neighbors(v)) + [v]:

                    # Count how many undominated vertices this candidate covers

                    undominated_neighbors_count = 0

                    for u in list(G.neighbors(neighbor)) + [neighbor]:

                        if not dominated[u]:

                            undominated_neighbors_count += 1



                    # Update the best vertex if this candidate covers more undominated vertices

                    if undominated_neighbors_count > best_undominated_count:

                        best_undominated_count = undominated_neighbors_count

                        best_vertex = neighbor



                # Add the best vertex to the dominating set for this component

                dominating_set.add(best_vertex)



                # Mark the neighbors of the best vertex as dominated

                for neighbor in G.neighbors(best_vertex):

                    dominated[neighbor] = True

                    # Mark the mirror vertex (i, 1-k) as dominated to reflect domination in the original graph

                    mirror_neighbor = (neighbor[0], 1 - neighbor[1])

                    dominated[mirror_neighbor] = True



        # Return the dominating set for this bipartite component

        return dominating_set



    # Validate that the input is a NetworkX Graph object

    if not isinstance(graph, nx.Graph):

        raise ValueError("Input must be an undirected NetworkX Graph.")



    # Handle edge cases: return an empty set if the graph has no nodes or no edges

    if graph.number_of_nodes() == 0 or graph.number_of_edges() == 0:

        return set()



    # Initialize the dominating set with all isolated nodes, as they must be included to dominate themselves

    approximate_dominating_set = set(nx.isolates(graph))

    # Remove isolated nodes from the graph to process the remaining components

    graph.remove_nodes_from(approximate_dominating_set)



    # If the graph is empty after removing isolated nodes, return the set of isolated nodes

    if graph.number_of_nodes() == 0:

        return approximate_dominating_set



    # Initialize an empty bipartite graph to transform the remaining graph

    bipartite_graph = nx.Graph()



    # Construct the bipartite graph B

    for i in graph.nodes():

        # Add an edge between mirror nodes (i, 0) and (i, 1) for each vertex i

        bipartite_graph.add_edge((i, 0), (i, 1))

        # Add edges reflecting adjacency in the original graph: (i, 0) to (j, 1) for each neighbor j

        for j in graph.neighbors(i):

            bipartite_graph.add_edge((i, 0), (j, 1))



    # Process each connected component in the bipartite graph

    for component in nx.connected_components(bipartite_graph):

        # Extract the subgraph for the current connected component

        bipartite_subgraph = bipartite_graph.subgraph(component)



        # Compute the dominating set for this component using the subroutine

        tuple_nodes = find_dominating_set_via_bipartite_proxy(bipartite_subgraph)



        # Extract the original node indices from the tuple nodes (i, k) and add them to the dominating set

        approximate_dominating_set.update({tuple_node[0] for tuple_node in tuple_nodes})



    # Return the final dominating set for the original graph

    return approximate_dominating_set

The algorithm transforms the problem into a bipartite graph setting and uses a greedy approach. Here are the steps:

1. 
   

   Handle Isolated Nodes:

   
   
   
   
   
   • Identify all isolated nodes in
     
     $G$
     
     (vertices with degree 0).
   
   
   • Add these nodes to the dominating set
     
     $S$
     
     , as they must be included to dominate themselves.
   
   
   
   


2. 
   

   Construct a Bipartite Graph
   
   $B$
   
   :

   
   
   
   
   
   • For the remaining graph (after removing isolated nodes), construct a bipartite graph
     
     $B$
     
     with:
     
     
     
     
     • 
       Vertex Set: Two partitions, where each vertex
       
       $i\in V$
       
       is duplicated as
       
       $(i,0)$
       
       and
       
       $(i,1)$
       
       .
     
     
     • 
       Edge Set:
     
     
     • An edge
       
       $(i,0)-(i,1)$
       
       for each
       
       $i\in V$
       
       .
     
     
     • For each edge
       
       $(i,j)\in E$
       
       in
       
       $G$
       
       , add edges
       
       $(i,0)-(j,1)$
       
       and
       
       $(j,0)-(i,1)$
       
       in
       
       $B$
       
       .
     
     
     
     
   
   
   
   


3. 
   

   Greedy Dominating Set in
   
   $B$
   
   :

   
   
   
   
   
   • Run a greedy algorithm on
     
     $B$
     
     to compute a dominating set
     
     DBD_BDB​
     
     :
     
     
     
     
     • While there are undominated vertices in
       
       $B$
       
       , select the vertex that dominates the maximum number of currently undominated vertices and add it to
       
       DBD_BDB​
       
       .
     
     
     
     
   
   
   
   


4. 
   

   Map Back to
   
   $G$
   
   :

   
   
   
   
   
   • Define the dominating set
     
     $S$
     
     for
     
     $G$
     
     as:
     
     
     
     
     • 
       
       S={i∈V∣(i,0)∈DB or (i,1)∈DB}S = \{ i \in V \mid (i, 0) \in D_B \text{ or } (i, 1) \in D_B \}S={i∈V∣(i,0)∈DB​ or (i,1)∈DB​}
       
       .
     
     
     
     
   
   
   • Include the isolated nodes identified in Step 1.
   
   
   
   

Correctness of the Algorithm

Let’s verify that

$S$

is a dominating set for

$G$

:

• 
  

  Isolated Nodes:

  
  
  
  
  
  • All isolated nodes are explicitly added to
    
    $S$
    
    , so they are dominated by themselves.
  
  
  
  


• 
  

  Non-Isolated Nodes:

  
  
  
  
  
  • Consider any vertex
    
    $i\in V$
    
    in the non-isolated part of
    
    $G$
    
    :
  
  
  • 
    Case 1:
    
    $i\in S$
    
    :
    
    
    
    
    • If
      
      $(i,0)$
      
      or
      
      $(i,1)$
      
      is in
      
      DBD_BDB​
      
      , then
      
      $i\in S$
      
      , and
      
      $i$
      
      is dominated by itself.
    
    
    
    
  
  
  • 
    Case 2:
    
    $i\notin S$
    
    :
    
    
    
    
    • If neither
      
      $(i,0)$
      
      nor
      
      $(i,1)$
      
      is in
      
      DBD_BDB​
      
      , then since
      
      DBD_BDB​
      
      dominates all vertices in
      
      $B$
      
      ,
      
      $(i,0)$
      
      must be adjacent to some
      
      (j,1)∈DB(j, 1) \in D_B(j,1)∈DB​
      
      .
    
    
    • In
      
      $B$
      
      ,
      
      $(i,0)-(j,1)$
      
      exists if
      
      $(i,j)\in E$
      
      in
      
      $G$
      
      .
    
    
    • Thus,
      
      $j\in S$
      
      (because
      
      (j,1)∈DB(j, 1) \in D_B(j,1)∈DB​
      
      ), and
      
      $i$
      
      is adjacent to
      
      $j$
      
      in
      
      $G$
      
      .
    
    
    
    
  
  
  
  


• 
  

  Conclusion:

  
  
  
  
  
  • Every vertex in
    
    $G$
    
    is either in
    
    $S$
    
    or has a neighbor in
    
    $S$
    
    , so
    
    $S$
    
    is a dominating set.
  
  
  
  

Approximation Analysis Using

DuD_uDu​

To prove that

$|S|\le 2\cdot |OPT|$

, we associate each vertex in the optimal dominating set

$OPT$

of

$G$

with vertices in

$S$

, ensuring that each vertex in

$OPT$

is “responsible” for at most two vertices in

$S$

.

Definitions

• Let
  
  $OPT$
  
  be a minimum dominating set of
  
  $G$
  
  .


• For each vertex
  
  $u\in OPT$
  
  , define
  
  Du⊆SD_u \subseteq SDu​⊆S
  
  as the set of vertices in
  
  $S$
  
  that are charged to
  
  $u$
  
  based on how the greedy algorithm selects vertices in
  
  $B$
  
  to dominate vertices related to
  
  $u$
  
  .

Key Idea

The

DuD_uDu​

analysis shows that the greedy algorithm selects at most two vertices per vertex in

$OPT$

due to the graph’s structure. Here, we mirror this by analyzing the bipartite graph

$B$

and the mapping back to

$G$

, showing that each

$u\in OPT$

contributes to at most two vertices being added to

$S$

.

Analysis Steps

1. 
   

   Role of
   
   $OPT$
   
   in
   
   $G$
   
   :

   
   
   
   
   
   • Each
     
     $u\in OPT$
     
     dominates itself and its neighbors in
     
     $G$
     
     .
   
   
   • In
     
     $B$
     
     , the vertices
     
     $(u,0)$
     
     and
     
     $(u,1)$
     
     correspond to
     
     $u$
     
     , and we need to ensure they (and their neighbors) are dominated by
     
     DBD_BDB​
     
     .
   
   
   
   


2. 
   

   Greedy Selection in
   
   $B$
   
   :

   
   
   
   
   
   • The greedy algorithm selects a vertex
     
     $w=(j,k)$
     
     (where
     
     $k=0$
     
     or
     
     $1$
     
     ) in
     
     $B$
     
     to maximize the number of undominated vertices covered.
   
   
   • When
     
     $w$
     
     is added to
     
     DBD_BDB​
     
     ,
     
     $j$
     
     is added to
     
     $S$
     
     .
   
   
   
   


3. 
   

   Defining
   
   DuD_uDu​
   
   :

   
   
   
   
   
   • For each
     
     $u\in OPT$
     
     ,
     
     DuD_uDu​
     
     includes vertices
     
     $j\in S$
     
     such that the selection of
     
     $(j,0)$
     
     or
     
     $(j,1)$
     
     in
     
     DBD_BDB​
     
     helps dominate
     
     $(u,0)$
     
     or
     
     $(u,1)$
     
     .
   
   
   • We charge
     
     $j$
     
     to
     
     $u$
     
     if:
     
     
     
     
     • 
       
       $j=u$
       
       (i.e.,
       
       $(u,0)$
       
       or
       
       $(u,1)$
       
       is selected), or
     
     
     • 
       
       $j$
       
       is a neighbor of
       
       $u$
       
       in
       
       $G$
       
       , and selecting
       
       $(j,k)$
       
       dominates
       
       $(u,0)$
       
       or
       
       $(u,1)$
       
       via an edge in
       
       $B$
       
       .
     
     
     
     
   
   
   
   


4. 
   

   Bounding
   
   ∣Du∣|D_u|∣Du​∣
   
   :

   
   
   
   
   
   • 
     Case 1:
     
     $u\in S$
     
     :
     
     
     
     
     • If
       
       $(u,0)$
       
       or
       
       $(u,1)$
       
       is selected in
       
       DBD_BDB​
       
       , then
       
       $u\in S$
       
       .
     
     
     • Selecting
       
       $(u,1)$
       
       dominates
       
       $(u,0)$
       
       (via
       
       $(u,0)-(u,1)$
       
       ), and vice versa.
     
     
     • At most one vertex (
       
       $u$
       
       ) is added to
       
       $S$
       
       for
       
       $u$
       
       , so
       
       ∣Du∣≤1|D_u| \leq 1∣Du​∣≤1
       
       in this case.
     
     
     
     
   
   
   • 
     Case 2:
     
     $u\notin S$
     
     :
     
     
     
     
     • Neither
       
       $(u,0)$
       
       nor
       
       $(u,1)$
       
       is in
       
       DBD_BDB​
       
       .
     
     
     • 
       
       $(u,0)$
       
       must be dominated by some
       
       (j,1)∈DB(j, 1) \in D_B(j,1)∈DB​
       
       , where
       
       $(u,j)\in E$
       
       in
       
       $G$
       
       , so
       
       $j\in S$
       
       .
     
     
     • 
       
       $(u,1)$
       
       must be dominated by some
       
       (k,0)∈DB(k, 0) \in D_B(k,0)∈DB​
       
       , where
       
       $(u,k)\in E$
       
       in
       
       $G$
       
       , so
       
       $k\in S$
       
       .
     
     
     • Thus,
       
       Du={j,k}D_u = \{ j, k \}Du​={j,k}
       
       , and
       
       ∣Du∣≤2|D_u| \leq 2∣Du​∣≤2
       
       (if
       
       $j=k$
       
       , then
       
       ∣Du∣=1|D_u| = 1∣Du​∣=1
       
       ).
     
     
     
     
   
   
   • 
     Greedy Optimization:
     
     
     
     
     • The greedy algorithm often selects a single vertex that dominates both
       
       $(u,0)$
       
       and
       
       $(u,1)$
       
       indirectly through neighbors, but in the worst case, two selections suffice.
     
     
     
     
   
   
   
   


5. 
   

   Total Size of
   
   $S$
   
   :

   
   
   
   
   
   • Each vertex
     
     $j\in S$
     
     corresponds to at least one selection
     
     (j,k)∈DB(j, k) \in D_B(j,k)∈DB​
     
     .
   
   
   • Since each
     
     $u\in OPT$
     
     has
     
     ∣Du∣≤2|D_u| \leq 2∣Du​∣≤2
     
     , the total number of vertices in
     
     $S$
     
     is:
     
     
     
     ∣S∣≤∑u∈OPT∣Du∣≤2⋅∣OPT∣|S| \leq \sum_{u \in OPT} |D_u| \leq 2 \cdot |OPT|
     ∣S∣≤u∈OPT∑​∣Du​∣≤2⋅∣OPT∣
     
     
     
     
     
   
   
   
   • This accounts for all selections each of which corresponds to a distinct
     
     
     $u\in OPT.$
     
     
     
   
   
   
   
   
   

Conclusion

• Each
  
  $u\in OPT$
  
  is associated with at most two vertices in
  
  $S$
  
  via the
  
  DuD_uDu​
  
  charging scheme.


• Thus,
  
  $|S|\le 2\cdot |OPT|$
  
  , proving the 2-approximation.

Conclusion

The algorithm computes a dominating set

$S$

for

$G$

by:

• Adding all isolated nodes to
  
  $S$
  
  .


• Constructing a bipartite graph
  
  $B$
  
  with vertices
  
  $(i,0)$
  
  and
  
  $(i,1)$
  
  for each
  
  $i\in V$
  
  and edges reflecting
  
  $G$
  
  ’s structure.


• Using a greedy algorithm to find a dominating set
  
  DBD_BDB​
  
  in
  
  $B$
  
  .


• Mapping back to
  
  S={i∣(i,0)∈DB or (i,1)∈DB}S = \{ i \mid (i, 0) \in D_B \text{ or } (i, 1) \in D_B \}S={i∣(i,0)∈DB​ or (i,1)∈DB​}
  
  .

$S$

is a dominating set because every vertex in

$G$

is either in

$S$

or adjacent to a vertex in

$S$

. By adapting the

DuD_uDu​

analysis from chordal graphs, we define

DuD_uDu​

for each

$u\in OPT$

as the vertices in

$S$

charged to

$u$

, showing

∣Du∣≤2|D_u| \leq 2∣Du​∣≤2

. This ensures

$|S|\le 2\cdot |OPT|$

, achieving a 2-approximation ratio for the dominating set problem in general undirected graphs.

Runtime Analysis of the Algorithm

To analyze the runtime of the find_dominating_set algorithm, we need to examine its key components and determine the time complexity of each step. The algorithm processes a graph to find a dominating set using a bipartite graph construction and a greedy subroutine. Below, we break down the analysis into distinct steps, assuming the input graph

$G$

has

$n$

nodes and

$m$

edges.

Step 1: Handling Isolated Nodes

The algorithm begins by identifying and handling isolated nodes (nodes with no edges) in the graph.

• 
  Identify Isolated Nodes: Using nx.isolates(graph) from the NetworkX library, isolated nodes are found by checking the degree of each node. This takes
  
  $O(n)$
  
  time, as there are
  
  $n$
  
  nodes to examine.


• 
  Remove Isolated Nodes: Removing a node in NetworkX is an
  
  $O(1)$
  
  operation per node. If there are
  
  $k$
  
  isolated nodes (where
  
  $k\le n$
  
  ), the total time to remove them is
  
  $O(k)$
  
  , which is bounded by
  
  $O(n)$
  
  .

Time Complexity for Step 1:

$O(n)$

Step 2: Constructing the Bipartite Graph

Next, the algorithm constructs a bipartite graph

$B$

based on the remaining graph after isolated nodes are removed.

• 
  Add Mirror Edges: For each node
  
  $i$
  
  in
  
  $G$
  
  , two nodes
  
  $(i,0)$
  
  and
  
  $(i,1)$
  
  are created in
  
  $B$
  
  , connected by an edge. With
  
  $n$
  
  nodes, and each edge addition being
  
  $O(1)$
  
  , this step takes
  
  $O(n)$
  
  time.


• 
  Add Adjacency Edges: For each edge
  
  $(i,j)$
  
  in
  
  $G$
  
  , edges
  
  $(i,0)-(j,1)$
  
  and
  
  $(j,0)-(i,1)$
  
  are added to
  
  $B$
  
  . Since
  
  $G$
  
  is undirected, each edge is processed once, and adding two edges per original edge takes
  
  $O(1)$
  
  time. With
  
  $m$
  
  edges, this is
  
  $O(m)$
  
  .

Time Complexity for Step 2:

$O(n+m)$

Step 3: Finding Connected Components

The algorithm identifies connected components in the bipartite graph

$B$

.

• 
  Compute Connected Components: Using nx.connected_components, this operation runs in
  
  O(n′+m′)O(n' + m')O(n′+m′)
  
  time, where
  
  n′n'n′
  
  and
  
  m′m'm′
  
  are the number of nodes and edges in
  
  $B$
  
  . In
  
  $B$
  
  , there are
  
  n′=2nn' = 2nn′=2n
  
  nodes (two per node in
  
  $G$
  
  ) and
  
  m′=n+2mm' = n + 2mm′=n+2m
  
  edges (
  
  $n$
  
  mirror edges plus
  
  $2m$
  
  adjacency edges). Thus, the time is
  
  $O(2n+(n+2m))=O(n+m)$
  
  .

Time Complexity for Step 3:

$O(n+m)$

Step 4: Computing Dominating Sets for Each Component

For each connected component in

$B$

, the subroutine find_dominating_set_via_bipartite_proxy computes a dominating set. We analyze this subroutine for a single component with

ncn_cnc​

nodes and

mcm_cmc​

edges, then scale to all components.

Subroutine Analysis: find_dominating_set_via_bipartite_proxy

• 
  

  Initialization:

  
  
  
  
  
  • Create a dominated dictionary:
    
    O(nc)O(n_c)O(nc​)
    
    .
  
  
  • Sort nodes by degree:
    
    O(nclog⁡nc)O(n_c \log n_c)O(nc​lognc​)
    
    .
  
  
  
  


• 
  

  Main Loop:

  
  
  
  
  
  • The loop continues until all nodes are dominated, running up to
    
    O(nc)O(n_c)O(nc​)
    
    iterations in the worst case.
  
  
  • For each iteration:
  
  
  • Select a node
    
    $v$
    
    and evaluate it and its neighbors (its closed neighborhood) to find the vertex that dominates the most undominated nodes.
  
  
  • For a node
    
    $v$
    
    with degree
    
    dvd_vdv​
    
    , there are
    
    dv+1d_v + 1dv​+1
    
    candidates (including
    
    $v$
    
    ).
  
  
  • For each candidate, count undominated nodes in its closed neighborhood, taking
    
    O(dcandidate)O(d_{\text{candidate}})O(dcandidate​)
    
    time per candidate.
  
  
  • Total time per iteration is
    
    O(dv+∑u∈N(v)du)O(d_v + \sum_{u \in N(v)} d_u)O(dv​+∑u∈N(v)​du​)
    
    , which is the sum of degrees in the closed neighborhood of
    
    $v$
    
    .
  
  
  • After selecting the best vertex, mark its neighbors and their mirrors as dominated, taking
    
    O(dbest)O(d_{\text{best}})O(dbest​)
    
    time.
  
  
  
  


• 
  

  Subroutine Total:

  
  
  
  
  
  • Sorting:
    
    O(nclog⁡nc)O(n_c \log n_c)O(nc​lognc​)
    
    .
  
  
  • Loop: Across all iterations, each node is processed once, and the total work is proportional to the sum of degrees, which is
    
    O(mc)O(m_c)O(mc​)
    
    .
  
  
  • Total for one component:
    
    O(nclog⁡nc+mc)O(n_c \log n_c + m_c)O(nc​lognc​+mc​)
    
    .
  
  
  
  

Across All Components

• The components are disjoint, with
  
  ∑nc=2n\sum n_c = 2n∑nc​=2n
  
  and
  
  ∑mc=n+2m\sum m_c = n + 2m∑mc​=n+2m
  
  .


• The total time is
  
  O(∑(nclog⁡nc+mc))O(\sum (n_c \log n_c + m_c))O(∑(nc​lognc​+mc​))
  
  .


• The
  
  ∑nclog⁡nc\sum n_c \log n_c∑nc​lognc​
  
  term is maximized when all nodes are in one component, yielding
  
  $O(2n\log 2n)=O(n\log n)$
  
  .


• The
  
  ∑mc=O(n+m)\sum m_c = O(n + m)∑mc​=O(n+m)
  
  .

Time Complexity for Step 4:

$O(n\log n+m)$

Overall Time Complexity

Combining all steps:

• Step 1:
  
  $O(n)$
  
  


• Step 2:
  
  $O(n+m)$
  
  


• Step 3:
  
  $O(n+m)$
  
  


• Step 4:
  
  $O(n\log n+m)$
  
  

The dominant term is

$O(n\log n+m)$

, so the overall time complexity of the find_dominating_set algorithm is

$O(n\log n+m)$

Space Complexity

• 
  Bipartite Graph:
  
  $O(n+m)$
  
  , with
  
  $2n$
  
  nodes and
  
  $n+2m$
  
  edges.


• 
  Auxiliary Data Structures: The dominated dictionary and undominated list use
  
  $O(n)$
  
  space.

Space Complexity:

$O(n+m)$

Conclusion

The find_dominating_set algorithm runs in

$O(n\log n+m)$

time and uses

$O(n+m)$

space, where

$n$

is the number of nodes and

$m$

is the number of edges in the input graph. The bottleneck arises from sorting nodes by degree in the subroutine, contributing the

$n\log n$

factor. This complexity makes the algorithm efficient and scalable for large graphs, especially given its 2-approximation guarantee for the dominating set problem.

Research Data

A Python implementation, titled Baldor: Approximate Minimum Dominating Set Solver—in tribute to the distinguished Cuban mathematician, educator, and jurist Aurelio Angel Baldor de la Vega, whose enduring pedagogical legacy shaped generations of thinkers—has been developed to efficiently solve the Approximate Dominating Set Problem. This implementation is publicly accessible through the Python Package Index (PyPI): https://pypi.org/project/baldor/. By constructing an approximate solution, the algorithm guarantees an approximation ratio of at most 2 for the Dominating Set Problem.

Table: Code Metadata

Experimental Results

Methodology and Experimental Setup

To evaluate our algorithm rigorously, we use the benchmark instances from the Second DIMACS Implementation Challenge [Johnson1996]. These instances are widely recognized in the computational graph theory community for their diversity and hardness, making them ideal for testing algorithms on the minimum dominating set problem.

The experiments were conducted on a system with the following specifications:

• 
  Processor: 11th Gen Intel® Core™ i7-1165G7 (2.80 GHz, up to 4.70 GHz with Turbo Boost)


• 
  Memory: 32 GB DDR4 RAM


• 
  Operating System: Windows 10 Pro (64-bit)

Our algorithm was implemented using Baldor: Approximate Minimum Dominating Set Solver (v0.1.2) [Vega25], a custom implementation designed to achieve a 2-approximation guarantee for the minimum dominating set problem. As a baseline for comparison, we employed the weighted dominating set approximation algorithm provided by NetworkX [Vazirani2001], which guarantees a solution within a logarithmic approximation ratio of

$\log |V|\cdot OPT$

, where

$OPT$

is the size of the optimal dominating set and

$|V|$

is the number of vertices in the graph.

Each algorithm was run on the same set of DIMACS instances, and the results were recorded to ensure a fair comparison. We repeated each experiment three times and report the average runtime to account for system variability.

Performance Metrics

We evaluate the performance of our algorithm using the following metrics:

1. 
   Runtime (milliseconds): The total computation time required to compute the dominating set, measured in milliseconds. This metric reflects the algorithm's efficiency and scalability on graphs of varying sizes.


2. 
   Approximation Quality: To quantify the quality of the solutions produced by our algorithm, we compute the upper bound on the approximation ratio, defined as:

where:

• 
  
  ∣OPTB∣|OPT_B|∣OPTB​∣
  
  : The size of the dominating set produced by our algorithm (Baldor).


• 
  
  ∣OPTW∣|OPT_W|∣OPTW​∣
  
  : The size of the dominating set produced by the NetworkX baseline.


• 
  
  $|V|$
  
  : The number of vertices in the graph.

Given the theoretical guarantees, NetworkX ensures

∣OPTW∣≤log⁡∣V∣⋅OPT|OPT_W| \leq \log |V| \cdot OPT∣OPTW​∣≤log∣V∣⋅OPT

, and our algorithm guarantees

∣OPTB∣≤2⋅OPT|OPT_B| \leq 2 \cdot OPT∣OPTB​∣≤2⋅OPT

, where

$OPT$

is the optimal dominating set size (unknown in practice). Thus, the metric

log⁡∣V∣⋅∣OPTB∣∣OPTW∣\log |V| \cdot \frac{|OPT_B|}{|OPT_W|}log∣V∣⋅∣OPTW​∣∣OPTB​∣​

provides insight into how close our solution is to the theoretical 2-approximation bound. A value near 2 indicates that our algorithm is performing near-optimally relative to the baseline.

Results and Analysis

The experimental results for a subset of the DIMACS instances are listed below. Each entry includes the dominating set size and runtime (in milliseconds) for our algorithm (

∣OPTB∣|OPT_B|∣OPTB​∣

) and the NetworkX baseline (

∣OPTW∣|OPT_W|∣OPTW​∣

), along with the computed approximation quality metric

log⁡∣V∣⋅∣OPTB∣∣OPTW∣\log |V| \cdot \frac{|OPT_B|}{|OPT_W|}log∣V∣⋅∣OPTW​∣∣OPTB​∣​

.

• 
  p_hat500-1.clq:
  
  ∣OPTB∣=10|OPT_B| = 10∣OPTB​∣=10
  
  (259.872 ms),
  
  ∣OPTW∣=14|OPT_W| = 14∣OPTW​∣=14
  
  (37.267 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=4.439006\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 4.439006log∣V∣⋅∣OPTW​∣∣OPTB​∣​=4.439006
  
  


• 
  p_hat500-2.clq:
  
  ∣OPTB∣=5|OPT_B| = 5∣OPTB​∣=5
  
  (535.828 ms),
  
  ∣OPTW∣=7|OPT_W| = 7∣OPTW​∣=7
  
  (31.832 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=4.439006\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 4.439006log∣V∣⋅∣OPTW​∣∣OPTB​∣​=4.439006
  
  


• 
  p_hat500-3.clq:
  
  ∣OPTB∣=3|OPT_B| = 3∣OPTB​∣=3
  
  (781.632 ms),
  
  ∣OPTW∣=3|OPT_W| = 3∣OPTW​∣=3
  
  (19.985 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=6.214608\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 6.214608log∣V∣⋅∣OPTW​∣∣OPTB​∣​=6.214608
  
  


• 
  p_hat700-1.clq:
  
  ∣OPTB∣=10|OPT_B| = 10∣OPTB​∣=10
  
  (451.447 ms),
  
  ∣OPTW∣=22|OPT_W| = 22∣OPTW​∣=22
  
  (70.044 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=2.977764\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 2.977764log∣V∣⋅∣OPTW​∣∣OPTB​∣​=2.977764
  
  


• 
  p_hat700-2.clq:
  
  ∣OPTB∣=6|OPT_B| = 6∣OPTB​∣=6
  
  (1311.585 ms),
  
  ∣OPTW∣=8|OPT_W| = 8∣OPTW​∣=8
  
  (69.925 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=4.913310\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 4.913310log∣V∣⋅∣OPTW​∣∣OPTB​∣​=4.913310
  
  


• 
  p_hat700-3.clq:
  
  ∣OPTB∣=3|OPT_B| = 3∣OPTB​∣=3
  
  (1495.283 ms),
  
  ∣OPTW∣=3|OPT_W| = 3∣OPTW​∣=3
  
  (72.238 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=6.551080\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 6.551080log∣V∣⋅∣OPTW​∣∣OPTB​∣​=6.551080
  
  


• 
  san1000.clq:
  
  ∣OPTB∣=4|OPT_B| = 4∣OPTB​∣=4
  
  (1959.679 ms),
  
  ∣OPTW∣=40|OPT_W| = 40∣OPTW​∣=40
  
  (630.204 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=0.690776\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 0.690776log∣V∣⋅∣OPTW​∣∣OPTB​∣​=0.690776
  
  


• 
  san200_0.7_1.clq:
  
  ∣OPTB∣=3|OPT_B| = 3∣OPTB​∣=3
  
  (93.572 ms),
  
  ∣OPTW∣=4|OPT_W| = 4∣OPTW​∣=4
  
  (5.196 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=3.973738\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 3.973738log∣V∣⋅∣OPTW​∣∣OPTB​∣​=3.973738
  
  


• 
  san200_0.7_2.clq:
  
  ∣OPTB∣=3|OPT_B| = 3∣OPTB​∣=3
  
  (103.698 ms),
  
  ∣OPTW∣=5|OPT_W| = 5∣OPTW​∣=5
  
  (6.463 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=3.178990\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 3.178990log∣V∣⋅∣OPTW​∣∣OPTB​∣​=3.178990
  
  


• 
  san200_0.9_1.clq:
  
  ∣OPTB∣=2|OPT_B| = 2∣OPTB​∣=2
  
  (115.282 ms),
  
  ∣OPTW∣=2|OPT_W| = 2∣OPTW​∣=2
  
  (0.000 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=5.298317\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 5.298317log∣V∣⋅∣OPTW​∣∣OPTB​∣​=5.298317
  
  


• 
  san200_0.9_2.clq:
  
  ∣OPTB∣=2|OPT_B| = 2∣OPTB​∣=2
  
  (120.091 ms),
  
  ∣OPTW∣=2|OPT_W| = 2∣OPTW​∣=2
  
  (5.012 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=5.298317\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 5.298317log∣V∣⋅∣OPTW​∣∣OPTB​∣​=5.298317
  
  


• 
  san200_0.9_3.clq:
  
  ∣OPTB∣=2|OPT_B| = 2∣OPTB​∣=2
  
  (110.157 ms),
  
  ∣OPTW∣=3|OPT_W| = 3∣OPTW​∣=3
  
  (0.000 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=3.532212\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 3.532212log∣V∣⋅∣OPTW​∣∣OPTB​∣​=3.532212
  
  


• 
  san400_0.5_1.clq:
  
  ∣OPTB∣=4|OPT_B| = 4∣OPTB​∣=4
  
  (243.552 ms),
  
  ∣OPTW∣=24|OPT_W| = 24∣OPTW​∣=24
  
  (45.267 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=0.998577\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 0.998577log∣V∣⋅∣OPTW​∣∣OPTB​∣​=0.998577
  
  


• 
  san400_0.7_1.clq:
  
  ∣OPTB∣=3|OPT_B| = 3∣OPTB​∣=3
  
  (419.706 ms),
  
  ∣OPTW∣=6|OPT_W| = 6∣OPTW​∣=6
  
  (20.579 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=2.995732\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 2.995732log∣V∣⋅∣OPTW​∣∣OPTB​∣​=2.995732
  
  


• 
  san400_0.7_2.clq:
  
  ∣OPTB∣=3|OPT_B| = 3∣OPTB​∣=3
  
  (405.550 ms),
  
  ∣OPTW∣=6|OPT_W| = 6∣OPTW​∣=6
  
  (24.712 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=2.995732\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 2.995732log∣V∣⋅∣OPTW​∣∣OPTB​∣​=2.995732
  
  


• 
  san400_0.7_3.clq:
  
  ∣OPTB∣=3|OPT_B| = 3∣OPTB​∣=3
  
  (452.306 ms),
  
  ∣OPTW∣=9|OPT_W| = 9∣OPTW​∣=9
  
  (33.302 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=1.997155\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 1.997155log∣V∣⋅∣OPTW​∣∣OPTB​∣​=1.997155
  
  


• 
  san400_0.9_1.clq:
  
  ∣OPTB∣=2|OPT_B| = 2∣OPTB​∣=2
  
  (453.124 ms),
  
  ∣OPTW∣=3|OPT_W| = 3∣OPTW​∣=3
  
  (20.981 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=3.994310\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 3.994310log∣V∣⋅∣OPTW​∣∣OPTB​∣​=3.994310
  
  


• 
  sanr200_0.7.clq:
  
  ∣OPTB∣=3|OPT_B| = 3∣OPTB​∣=3
  
  (96.323 ms),
  
  ∣OPTW∣=4|OPT_W| = 4∣OPTW​∣=4
  
  (7.047 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=3.973738\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 3.973738log∣V∣⋅∣OPTW​∣∣OPTB​∣​=3.973738
  
  


• 
  sanr200_0.9.clq:
  
  ∣OPTB∣=2|OPT_B| = 2∣OPTB​∣=2
  
  (116.587 ms),
  
  ∣OPTW∣=2|OPT_W| = 2∣OPTW​∣=2
  
  (2.892 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=5.298317\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 5.298317log∣V∣⋅∣OPTW​∣∣OPTB​∣​=5.298317
  
  


• 
  sanr400_0.5.clq:
  
  ∣OPTB∣=6|OPT_B| = 6∣OPTB​∣=6
  
  (340.535 ms),
  
  ∣OPTW∣=7|OPT_W| = 7∣OPTW​∣=7
  
  (20.473 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=5.135541\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 5.135541log∣V∣⋅∣OPTW​∣∣OPTB​∣​=5.135541
  
  


• 
  sanr400_0.7.clq:
  
  ∣OPTB∣=3|OPT_B| = 3∣OPTB​∣=3
  
  (490.877 ms),
  
  ∣OPTW∣=5|OPT_W| = 5∣OPTW​∣=5
  
  (22.703 ms),
  
  log⁡∣V∣⋅∣OPTB∣∣OPTW∣=3.594879\log |V| \cdot \frac{|OPT_B|}{|OPT_W|} = 3.594879log∣V∣⋅∣OPTW​∣∣OPTB​∣​=3.594879