Repository: networkx/networkx (python)

Issue:
min_weighted_dominating_set implementation problem

<!-- If you have a general question about NetworkX, please use the discussions tab to create a new discussion -->

<!--- Provide a general summary of the issue in the Title above -->

### Current Behavior

<!--- Tell us what happens instead of the expected behavior -->
First of all, I would like to clarify that I am in no way an expert in the subject, so its possible that I am misunderstanding something.
I have a network (with unweighted vertices) that is highly connected and I needed the dominating set. I tried both functions available in networkx for this purpose. I expected that [min_weighted_dominating_set](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.approximation.dominating_set.min_weighted_dominating_set.html#min-weighted-dominating-set) would get a set with at most the same number of members than [dominating_set](https://networkx.org/documentation/stable/reference/algorithms/generated/networkx.algorithms.dominating.dominating_set.html#dominating-set) since the last one just adds arbitrary nodes from the remaning nodes, but in my use case this was not the case.

a toy example:
```python3
import networkx as nx
graph = nx.complete_graph(5)
graph.add_edge(4, 5)
graph.add_edge(5, 6)
print(nx.algorithms.dominating_set(graph)) # {0, 5}
print(nx.algorithms.approximation.min_weighted_dominating_set(graph)) # {0, 1, 2, 4, 5}
```
I think that the problem is that in this line:
https://github.com/networkx/networkx/blob/c2bb296ad5d8d821463d10cf09911dbafff7ca1b/networkx/algorithms/approximation/dominating_set.py#L92
we are substracting only `dom_set`, but the neighbors of the `dom_set` should also be substracted

### Expected Behavior

<!--- Tell us what should happen -->
An alternative that I am using is to calculate the intersection between `neighborhood` and `vertices` (the undominated nodes):
```python3
    def _cost(node_and_neighborhood):
        """Returns the cost-effectiveness of greedily choosing the given
        node.

        `node_and_neighborhood` is a two-tuple comprising a node and its
        closed neighborhood.

        """
        v, neighborhood = node_and_neighborhood
        # return G.nodes[v].get(weight, 1) / len(neighborhood - dom_set)
        length = len(neighborhood & vertices)
        if length == 0:
            return float("inf")
        return G.nodes[v].get(weight, 1) / length
```
with this cost function the result in the example is `{4, 5}`. Selecting first the most connected node (4), and then adding 5 to dominate 6.  


### Steps to Reproduce

<!--- Provide a minimal example that reproduces the bug -->

### Environment

<!--- Please provide details about your local environment -->

Python version: 3.13.12
NetworkX version: 3.6.1

### Additional context

<!--- Add any other context about the problem here, screenshots, etc. -->
While trying to understand the problem I read the cited reference (Vazirani, Vijay V. Approximation Algorithms. Springer Science & Business Media, 2001). However, I could not understand the algorithm described in there. Instead, I used this one:
Potluri, A., & Singh, A. (2013). Hybrid metaheuristic algorithms for minimum weight dominating set. Applied Soft Computing, 13(1), 76–88. https://doi.org/10.1016/j.asoc.2012.07.009
where it describes various cost function for the greedy algorithm, including this one (eq 1; it uses max instead of min). These are the relevant lines:

> 4. Greedy heuristics for minimum weight dominating set
> We experimented with four different variations of a greedy heuristic to determine the minimum weight dominating set. In every algorithm, initially all nodes are colored WHITE. A node that is included in the dominating set is colored BLACK, whereas all nodes adjacent to the dominating node are colored GREY. We halt the algorithm when no WHITE nodes exist in the graph.
> In the first heuristic, we use an algorithm based on the standard greedy algorithm for the weighted set-cover problem [19]. The dominating set being constructed, D, is initialized to a NULL set in the beginning. The white degree of a node, d(u), is the number of WHITE neighbors of a given node u. For computing the minimum weight dominating set, we divide the white degree of the node, d(u), by the weight of the node w(u) and add the node with the maximum ratio to the dominating set D.



Patch:
diff --git a/networkx/algorithms/approximation/dominating_set.py b/networkx/algorithms/approximation/dominating_set.py
index e568a827ff9..b9786e8d755 100644
--- a/networkx/algorithms/approximation/dominating_set.py
+++ b/networkx/algorithms/approximation/dominating_set.py
@@ -1,7 +1,7 @@
 """Functions for finding node and edge dominating sets.
 
-A `dominating set`_ for an undirected graph *G* with vertex set *V*
-and edge set *E* is a subset *D* of *V* such that every vertex not in
+A `dominating set`_ for an undirected graph *G* with node set *V*
+and edge set *E* is a subset *D* of *V* such that every node not in
 *D* is adjacent to at least one member of *D*. An `edge dominating set`_
 is a subset *F* of *E* such that every edge not in *F* is
 incident to an endpoint of at least one edge in *F*.
@@ -48,7 +48,7 @@ def min_weighted_dominating_set(G, weight=None):
     --------
     >>> G = nx.Graph([(0, 1), (0, 4), (1, 4), (1, 2), (2, 3), (3, 4), (2, 5)])
     >>> nx.approximation.min_weighted_dominating_set(G)
-    {1, 2, 4}
+    {1, 2}
 
     Raises
     ------
@@ -89,26 +89,31 @@ def _cost(node_and_neighborhood):
 
         """
         v, neighborhood = node_and_neighborhood
-        return G.nodes[v].get(weight, 1) / len(neighborhood - dom_set)
-
-    # This is a set of all vertices not already covered by the
-    # dominating set.
-    vertices = set(G)
-    # This is a dictionary mapping each node to the closed neighborhood
-    # of that node.
+        # Use the intersection with uncovered nodes, not just the
+        # difference with the dominating set.  A node's neighbors may
+        # already be dominated (covered by an adjacent dom_set member)
+        # without being in dom_set themselves.  See #8523.
+        uncovered = len(neighborhood & uncovered_nodes)
+        if uncovered == 0:
+            return float("inf")
+        return G.nodes[v].get(weight, 1) / uncovered
+
+    # A set of all nodes not yet covered by the dominating set.
+    uncovered_nodes = set(G)
+    # A dict mapping each node to its closed neighborhood.
     neighborhoods = {v: {v} | set(G[v]) for v in G}
 
-    # Continue until all vertices are adjacent to some node in the
+    # Continue until all nodes are adjacent to some node in the
     # dominating set.
-    while vertices:
+    while uncovered_nodes:
         # Find the most cost-effective node to add, along with its
         # closed neighborhood.
         dom_node, min_set = min(neighborhoods.items(), key=_cost)
-        # Add the node to the dominating set and reduce the remaining
-        # set of nodes to cover.
+        # Add the node to the dominating set and reduce the
+        # remaining set of nodes to cover.
         dom_set.add(dom_node)
         del neighborhoods[dom_node]
-        vertices -= min_set
+        uncovered_nodes -= min_set
 
     return dom_set
 


Test patch:
diff --git a/networkx/algorithms/approximation/tests/test_dominating_set.py b/networkx/algorithms/approximation/tests/test_dominating_set.py
index 6b90d85ecf7..d0ae6f01f58 100644
--- a/networkx/algorithms/approximation/tests/test_dominating_set.py
+++ b/networkx/algorithms/approximation/tests/test_dominating_set.py
@@ -44,6 +44,22 @@ def test_null_graph(self):
         G = nx.Graph()
         assert min_weighted_dominating_set(G) == set()
 
+    def test_cost_accounts_for_already_dominated(self):
+        """Tests that the greedy cost function considers nodes dominated by
+        neighbors of the dominating set, not just nodes in the set itself.
+
+        Regression test for #8523.
+        """
+        # K5 + path 4-5-6: nodes 0-4 form a clique, 5 and 6 hang off node 4.
+        # Any minimum dominating set has 2 nodes: one from the clique (0-4)
+        # and one from the tail (5 or 6). E.g. {0, 5}, {4, 6}, {2, 5}, etc.
+        graph = nx.complete_graph(5)
+        graph.add_edge(4, 5)
+        graph.add_edge(5, 6)
+        dom_set = min_weighted_dominating_set(graph)
+        assert nx.is_dominating_set(graph, dom_set)
+        assert len(dom_set) == 2
+
     def test_min_edge_dominating_set(self):
         graph = nx.path_graph(5)
         dom_set = min_edge_dominating_set(graph)