Source: DOMINATING SET (DecisionMinimumDominatingSet)
Target: MIN-SUM MULTICENTER (MinimumSumMulticenter)
Motivation: Establishes NP-completeness of MIN-SUM MULTICENTER (the p-median problem) via polynomial-time reduction from DOMINATING SET. The source is Decision<MinimumDominatingSet> which provides the bound parameter K.
Reference: Garey & Johnson, Computers and Intractability, ND51, p.220

GJ Source Entry

[ND51] MIN-SUM MULTICENTER
INSTANCE: Graph G=(V,E), weight w(v)∈Z_0^+ for each v∈V, length l(e)∈Z_0^+ for each e∈E, positive integer K≤|V|, positive rational number B.
QUESTION: Is there a set P of K "points on G" such that if d(v) is the length of the shortest path from v to the closest point in P, then Σ_{v∈V} d(v)·w(v)≤B?
Reference: [Kariv and Hakimi, 1976b]. Transformation from DOMINATING SET.
Comment: Also known as the "p-median" problem. It can be shown that there is no loss of generality in restricting P to being a subset of V. Remains NP-complete if w(v)=1 for all v∈V and l(e)=1 for all e∈E. Solvable in polynomial time for any fixed K and for arbitrary K if G is a tree.

Implementation Note

The source is Decision<MinimumDominatingSet<SimpleGraph, One>> (DecisionMinimumDominatingSet), which provides the bound parameter K via decision.k(). This resolves the optimization-vs-decision mismatch previously flagged in this issue.

Reduction Algorithm

Given a DecisionMinimumDominatingSet instance (G = (V, E), K) where K is the dominating set size bound, construct a MinimumSumMulticenter instance as follows:

1. Preserve graph: Use the same graph G = (V, E).
2. Set unit weights and lengths: w(v) = 1 for all v, l(e) = 1 for all e.
3. Set center count: k = K (same as dominating set size bound).
4. Set distance bound: B = |V| - K.

Note: This reduction requires the source graph G to be connected. For disconnected graphs, vertices in components without a center would have infinite distance, making the sum exceed any finite B. The reduction is valid when restricted to connected instances.

Correctness argument:

• (Forward) If D is a dominating set with |D| = K, placing centers at D gives: for each v ∈ D, d(v) = 0; for each v ∉ D, d(v) ≤ 1 (since v has a neighbor in D). Total = Σ d(v) ≤ 0·K + 1·(n-K) = n - K = B.
• (Backward) If centers P achieve Σ d(v) ≤ n - K with K centers, then the n - K non-center vertices each contribute d(v) ≥ 1 to the sum (each must reach some center). For the sum to be at most n - K, each non-center vertex must have d(v) = 1, meaning every non-center vertex is adjacent to some center. Thus P is a dominating set.

Key insight: With unit weights and unit lengths, a K-center placement achieves total distance exactly n - K if and only if every non-center vertex is adjacent to a center, which is precisely the dominating set condition.

Size Overhead

Symbols:

• n = num_vertices of source graph G
• m = num_edges of source graph G

Note: The target MinimumSumMulticenter has only num_vertices as a registered size field. The graph structure is preserved unchanged. The k parameter on the target is derived from the source's K bound (not a source size field getter), so it cannot be expressed as an overhead expression in the current system.

Validation Method

• Closed-loop test: reduce source Dominating Set decision instance to MinSumMulticenter (unit weights, unit lengths, B = n - K), solve target with BruteForce, extract solution (the set of center vertices), verify it is a valid dominating set on the original graph
• Verify that for the extracted solution, each non-center vertex is at distance exactly 1 from a center (confirming dominating set property)
• Compare with known results from literature: on a star graph K_{1,n-1}, the single center vertex is a dominating set of size 1, and should yield total distance n - 1

Example

Source instance (Dominating Set decision):
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 7 edges:

• Edges: {0,1}, {0,2}, {1,3}, {2,3}, {3,4}, {3,5}, {4,5}
• K = 2

Dominating set D = {0, 3}:

• N[0] = {0, 1, 2}
• N[3] = {1, 2, 3, 4, 5}
• N[0] ∪ N[3] = V ✓

Constructed target instance (MinSumMulticenter):

• Same graph G with 6 vertices and 7 edges
• w(v) = 1 for all v, l(e) = 1 for all e
• k = 2 centers, B = 6 - 2 = 4

Optimal solution mapping:

• Place centers at P = {0, 3}
• d(0) = 0 (center), d(1) = 1, d(2) = 1, d(3) = 0 (center), d(4) = 1, d(5) = 1
• Σ d(v)·w(v) = 0 + 1 + 1 + 0 + 1 + 1 = 4 = B ✓

Suboptimal feasible placements (k = 2):

• P = {1, 3}: d(0) = 1, d(1) = 0, d(2) = 2, d(3) = 0, d(4) = 1, d(5) = 1 → Σ = 5 > B. Vertex 2 is at distance 2 from nearest center, so {1, 3} is not a dominating set (vertex 2 not adjacent to either). ✗
• P = {0, 4}: d(0) = 0, d(1) = 1, d(2) = 1, d(3) = 2, d(4) = 0, d(5) = 1 → Σ = 5 > B. Vertex 3 is at distance 2, so {0, 4} is not a dominating set. ✗
• P = {3, 4}: d(0) = 2, d(1) = 1, d(2) = 1, d(3) = 0, d(4) = 0, d(5) = 1 → Σ = 5 > B. Vertex 0 is at distance 2, so {3, 4} is not a dominating set. ✗

Infeasibility for K = 1:
No single vertex dominates all of V in this graph:

• Center at 3 (highest degree): N[3] = {1, 2, 3, 4, 5}, misses vertex 0. Total distance = 2 + 1 + 1 + 0 + 1 + 1 = 6 > B = 5.
• Center at 0: N[0] = {0, 1, 2}, misses {3, 4, 5}. Total distance = 0 + 1 + 1 + 2 + 3 + 3 = 10 > B = 5.

Extraction: The set of center vertices {0, 3} achieving Σ d(v) = B is returned as the dominating set solution. Verified: N[0] ∪ N[3] = V ✓.

References

• [Kariv and Hakimi, 1976b]: [Kariv1976b] Oded Kariv and S. Louis Hakimi. "An Algorithmic Approach to Network Location Problems -- Part 2: The p-Medians." SIAM Journal on Applied Mathematics, 37(3):539–560, 1979. (Cited as "1976b" in Garey & Johnson, likely referencing an earlier technical report.)