Repository navigation
[Model] MinMaxMulticenter #330
Description
Motivation
MIN-MAX MULTICENTER (P126) from Garey & Johnson, A2 ND50. A classical NP-complete facility location problem, also known as the p-center problem. Given a graph with vertex weights and edge lengths, the goal is to place K service centers (points on the graph) so as to minimize the maximum weighted distance from any vertex to its nearest center. Arises in emergency facility location, network design, and service coverage optimization. Closely related to the dominating set problem: on unweighted unit-length graphs, a set of K vertices is a dominating set if and only if it is a K-center solution with radius 1.
Associated reduction rules:
- As target: R70 (DOMINATING SET -> MIN-MAX MULTICENTER)
Definition
Name: MinMaxMulticenter
Canonical name: p-Center Problem; also: Min-Max Multicenter, Vertex k-Center Problem
Reference: Garey & Johnson, Computers and Intractability, A2 ND50
Mathematical definition:
We implement the vertex-restricted variant (also NP-complete; see Slater, 1976), where centers must be chosen from V rather than arbitrary points on edges. The full GJ formulation allows centers on edge interiors, but the vertex-restricted version is standard in the combinatorial optimization literature and maps naturally to binary variables.
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 subset S ⊆ V with |S| = K such that if d(v) is the length of the shortest path from v to the closest vertex in S, then max{d(v)·w(v): v ∈ V} ≤ B?
This is a decision (satisfaction) problem: given K and B, determine feasibility. Metric = bool, implementing SatisfactionProblem.
Variables
- Count: n = |V| binary variables (one per vertex), representing candidate center locations (vertex-restricted variant).
- Per-variable domain: binary {0, 1} — whether vertex v is selected as a center
- Meaning: variable x_v = 1 if vertex v is chosen as a center location. Exactly K variables must be set to 1. The configuration is valid if max{d(v)·w(v): v ∈ V} ≤ B, where d(v) is the shortest weighted-path distance from v to the nearest selected center.
Schema (data type)
Type name: MinMaxMulticenter<G, W>
Variants: graph type parameter G, weight type parameter W
| Field | Type | Description |
|---|---|---|
graph |
G |
The underlying graph G = (V, E) |
vertex_weights |
Vec<W> |
Non-negative weight w(v) for each vertex v |
edge_lengths |
Vec<W> |
Non-negative length l(e) for each edge e |
k |
usize |
Number of centers to place (K) |
bound |
W |
The distance bound B |
Size fields: num_vertices() (= |V|), num_edges() (= |E|), num_centers() (= K)
Notes:
- This is a satisfaction (decision) problem:
Metric = bool, implementingSatisfactionProblem.
Complexity
- Decision complexity: NP-complete (Kariv and Hakimi, 1979; transformation from DOMINATING SET). Remains NP-complete even with unit weights and unit edge lengths, and also for the vertex-restricted variant (Slater, 1976).
- Best known exact algorithm: The vertex p-center problem on general graphs can be solved by binary search over O(|V|^2) distance thresholds, each requiring a dominating set feasibility check on a threshold graph (Minieka, 1970). Using the best dominating set algorithm O*(1.4969^
num_vertices) (van Rooij and Bodlaender, 2011), the overall complexity is O*(1.4969^num_vertices) with polynomial overhead. - Polynomial cases: Solvable in polynomial time for fixed K (Kariv and Hakimi, 1979), and for arbitrary K if G is a tree (Kariv and Hakimi, 1979). For the continuous variant, Drezner (1984) gives O(n^{2K+1}).
- Approximation: 2-approximation is optimal unless P=NP; no (2-epsilon)-approximation exists for any epsilon > 0 (Hsu and Nemhauser, 1979).
declare_variants!complexity string:"1.4969^num_vertices"— via binary search over distance thresholds + iterated dominating set (van Rooij & Bodlaender, 2011).- References:
- O. Kariv, S. L. Hakimi (1979). "An Algorithmic Approach to Network Location Problems. I: The p-Centers." SIAM J. Appl. Math., 37(3):513-538.
- W. L. Hsu, G. L. Nemhauser (1979). "Easy and hard bottleneck location problems." Discrete Appl. Math., 1(3):209-216.
- J. M. W. van Rooij, H. L. Bodlaender (2011). "Exact algorithms for dominating set." Discrete Appl. Math., 159(17):2147-2164.
- E. Minieka (1970). "The m-Center Problem." SIAM Review, 12(1):138-139.
- Z. Drezner (1984). "The p-centre problem — heuristic and optimal algorithms." Journal of the Operational Research Society, 35(8):741-748.
- P. J. Slater (1976). "R-domination in graphs." Journal of the ACM, 23(3):446-450.
Specialization
- This is a special case of: General facility location / bottleneck covering problems
- Known special cases:
- Vertex k-center: centers restricted to vertices (also NP-complete) — this is the variant we implement
- Unweighted unit-length variant: w(v)=1, l(e)=1 (NP-complete, equivalent to minimum dominating set)
- Tree graphs: polynomial-time solvable (Kariv and Hakimi, 1979)
- Fixed K: polynomial-time solvable
Extra Remark
Full book text:
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" (where a point on G can be either a vertex in V or a point on an edge e ∈ E, with e regarded as a line segment of length l(e)) such that if d(v) is the length of the shortest path from v to the closest point in P, then max{d(v)·w(v): v ∈ V} ≤ B?
Reference: [Kariv and Hakimi, 1976a]. Transformation from DOMINATING SET.
Comment: Also known as the "p-center" problem. 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 [Kariv and Hakimi, 1976a]. Variant in which we must choose a subset P ⊆ V is also NP-complete but solvable for fixed K and for trees [Slater, 1976].
How to solve
- It can be solved by (existing) bruteforce. Enumerate all C(n, K) subsets of K vertices; for each subset, compute all-pairs shortest paths and evaluate max{d(v)·w(v)}. Check feasibility against B.
- It can be solved by reducing to integer programming. Binary variable x_v for each vertex; minimize B subject to: for each vertex v, sum constraints ensuring at least one center is within distance B/w(v); exactly K centers selected (sum x_v = K).
- Other: Reduce to iterated dominating set checks at different distance thresholds (Minieka, 1970); branch-and-cut algorithms.
Example Instance
Graph G with 6 vertices {0, 1, 2, 3, 4, 5} and 7 edges, unit weights and lengths:
- Edges: {0,1}, {1,2}, {2,3}, {3,4}, {4,5}, {0,5}, {1,4}
- K = 2, B = 1
Shortest path distances (unit edge lengths):
All edge lengths l(e) = 1, all vertex weights w(v) = 1.
Optimal 2-center: Place centers at vertices {1, 4}.
- d(0) = dist(0, {1,4}) = dist(0,1) = 1. w(0)·d(0) = 1 ≤ 1 ✓
- d(1) = 0 (center). ✓
- d(2) = dist(2, {1,4}) = min(dist(2,1), dist(2,4)) = min(1, 2) = 1. ✓
- d(3) = dist(3, {1,4}) = min(dist(3,1), dist(3,4)) = min(2, 1) = 1. ✓
- d(4) = 0 (center). ✓
- d(5) = dist(5, {1,4}) = min(dist(5,1), dist(5,4)) = min(2, 1) = 1. ✓
- max{d(v)·w(v)} = 1 ≤ B = 1 ✓
Note: This is equivalent to asking whether {1, 4} is a dominating set of G (since unit weights and lengths). Indeed, N[1] = {0,1,2,4} and N[4] = {1,3,4,5}, so N[1] ∪ N[4] = V. ✓
Activity
zazabap commentedon Mar 11, 2026
Issue Quality Check — Model
Overall: 2 passed, 0 failed, 2 warnings
Usefulness
The problem does not exist in the current codebase (
pred show MinMaxMulticenterreturns "Unknown problem"). The motivation is concrete: classical facility location problem (GJ A2 ND50), with a planned reduction from MinimumDominatingSet. The issue correctly notes the special-case equivalence between p-center with unit weights/lengths and dominating set. The problem would add a new node to the reduction graph with at least one incoming edge. Pass.Non-trivial
MinMaxMulticenter is genuinely distinct from all 24 existing problems:
Pass.
Correctness
References verified:
Kariv and Hakimi (1979): Confirmed. "An Algorithmic Approach to Network Location Problems. I: The p-Centers," SIAM J. Appl. Math., 37(3):513-538. Paper exists and establishes NP-completeness of the p-center problem and polynomial-time solvability on trees. The issue's citation details are accurate.
Hsu and Nemhauser (1979): Confirmed. "Easy and hard bottleneck location problems," Discrete Appl. Math., 1(3):209-216. The 2-approximation inapproximability result (no (2-epsilon)-approximation unless P=NP) is correct. Minor discrepancy: the issue cites pages "209-215" but the actual paper is pages 209-216. Not a substantive error.
van Rooij and Bodlaender (2011): Confirmed. "Exact algorithms for dominating set," Discrete Appl. Math., 159(17):2147-2164. The O*(1.4969^n) bound for dominating set is correct and already in the project bibliography (
vanrooij2011).Complexity claim: The issue claims O*(1.4969^n) for vertex p-center via "O(n^2) calls to a dominating set decision oracle (binary search on distance thresholds)." This is a reasonable argument: the vertex k-center problem on unweighted graphs can be solved by binary search over O(n^2) distance thresholds, each requiring a dominating set check. However, this indirect argument is not explicitly stated in any of the cited papers — it is an inference. For the weighted case with arbitrary edge lengths, the reduction to iterated dominating set is more nuanced. This warrants a Warn rather than a fail: the claim is plausible but should cite a specific source that establishes this reduction formally (e.g., Minieka 1970 or a textbook treatment).
Drezner (1984) claim: The issue cites "Drezner, 1984" for O(n^{2K+1}) for fixed K. The search results suggest this is from Drezner (1984) for the continuous p-center. For the discrete (vertex-restricted) case, Kariv and Hakimi (1979) already establish polynomial-time solvability for fixed K. The specific exponent 2K+1 may refer to Drezner's continuous variant — no full citation (title, journal) is provided.
Well-written
4a — Information Completeness: All required sections are present and substantive: Motivation, Name, Reference, Definition, Variables, Schema, Complexity, How to solve, Example Instance. No placeholder text. Good.
4b — Definition Completeness: The formal definition is complete and well-stated, directly from Garey & Johnson. Feasibility constraints and the decision question are clearly separated. Good.
4c — Issues found:
Definition vs Variables inconsistency: The formal definition says centers can be "points on G" (vertices OR points on edge interiors). The Variables section restricts to vertex-only placement: "n = |V| binary variables (one per vertex)." The issue acknowledges this ("the vertex-restricted variant... uses vertex-only placement") but the mismatch between the formal definition and the implementation scope should be resolved explicitly. Recommendation: Either restrict the definition to the vertex k-center variant from the start, or clarify that the implementation covers the vertex-restricted case and state the formal definition of that variant separately.
Decision vs Optimization ambiguity: The Schema notes say "This is a satisfaction (decision) problem in the GJ formulation: Metric = bool" but then also says "Alternatively, the optimization version minimizes the bottleneck radius B." The issue needs to pick one. Most problems in this codebase pick one formulation. Since the planned reduction from MinimumDominatingSet (an optimization problem with
SolutionSize<W>) would most naturally target a satisfaction formulation (given K centers, is radius at most B?), the decision version makes sense. But this should be stated definitively, not as "alternatively."Missing symbol definition: The complexity section references "O*(1.4969^n)" without defining what n is in context (presumably |V|). The
declare_variants!complexity string would need to usenum_vertices, which should be stated.Drezner citation incomplete: "Drezner, 1984" lacks a full citation (title, journal, pages). All other references have full details.
4d — Example Quality: The example is good — 6 vertices, 7 edges, K=2, B=1, fully worked with shortest path distances verified for each vertex. The dominating set equivalence is nicely demonstrated. The example is non-trivial and brute-force verifiable.
Recommendations
Add plan for #330: MinMaxMulticenter model
zazabap commentedon Mar 13, 2026
Fix-issue changelog
graphfield type fromSimpleGraphto genericGMinMaxMulticenter<G, W>with explicit type parametersdeclare_variants!complexity string:"1.4969^num_vertices"(via binary search + dominating set, van Rooij & Bodlaender 2011)**Size fields:**line (moved out of Notes)Applied by
/fix-issue.GiggleLiu commentedon Mar 21, 2026
Please kindly check the following items (PR #630):
cargo install --path problemreductions-cli):💬 Join the discussion on Zulip — feel free to ask questions or leave feedback there.
Fix #330: Add MinMaxMulticenter (p-Center) model (#630)