3-SAT → Allowed-centers min-sum-radii on unweighted graph metrics Complexity open
Unsolved
Why this question matters
Moderate: classical hardness would finish the basic complexity picture for a natural facility-location restriction and clarify the effect of admissible sites. The result would not settle unrestricted unweighted MSR, for which a randomized quasipolynomial algorithm is known.
Kumar and coauthors explicitly leave classical NP-hardness of Allowed-Centers-MSR on unweighted graph metrics open, despite proving W[1]-hardness under parameterized reductions. Exact-MSR is already NP-hard and is a different requirement.
The reduction to construct
An explicit Boolean 3-CNF formula is given, with YES if satisfiable and NO otherwise.
An explicitly encoded connected simple unweighted graph G, a nonempty set A of allowed center vertices, integers k and D in binary are given. The answer is YES exactly when at most k pairs (center c in A, nonnegative integer radius r) cover every vertex within its graph distance from some chosen center and the sum of radii is at most D; otherwise NO. Zero-radius singleton clusters are allowed.
Build deterministic polynomial-time F and G from 3-SAT to this exact Allowed-Centers-MSR decision problem on unweighted graph metrics, with equivalent answers and all-output recovery. A positive result would prove classical NP-hardness, which is not supplied by the published parameterized reduction.
High: the published W[1]-hardness route subdivides weighted edges and permits parameter-dependent growth that does not automatically yield a polynomial many-one reduction. A possible route is a direct set-cover-style graph gadget with radii one and two, while preventing zero-radius centers from evading the budget; no such route has been tested.
What a complete answer must include
Give an explicit polynomial-size unweighted graph, allowed-center set and budgets; prove both directions including zero-radius clusters and all chosen centers; provide bit bounds and a valid decoder. Later tests should compare answers with independent exhaustive clustering on small graphs.
References
Literature checked 2026-09-26. Checked the SWAT 2026 primary paper's formal definition, Theorems 12-14 and Conclusion; searched 2026-09-26 for 'Allowed-Centers-MSR NP-hard unweighted' and later versions. No later classical hardness theorem surfaced. Gates 1-4 pass; Gate 5 holds on a polynomial-size unweighted gadget; Gate 6 was not assessed.