Weighted Centers on Bounded-Dimensional Median Graphs

Definitions and mathematical statement

For a finite connected undirected graph $G=(V,E)$, let $d_G(u,v)$ be the minimum number of edges in a path from $u$ to $v$, and define the interval \[ I_G(u,v)=\{x\in V:d_G(u,v)=d_G(u,x)+d_G(x,v)\}. \] The graph is a median graph if, for every $u,v,w\in V$, the intersection \[ I_G(u,v)\cap I_G(v,w)\cap I_G(w,u) \] contains exactly one vertex. Let $Q_k$ be the graph on $\{0,1\}^k$ whose adjacent vertices differ in exactly one coordinate. The cube dimension of a median graph is the largest integer $k\geq 0$ for which it contains an isometric copy of $Q_k$. Bounded cube dimension means that this dimension is at most a fixed constant $D$, independent of the number of vertices.

For the ordinary vertex Center problem, the eccentricity and radius are \[ e_G(v)=\max_{u\in V}d_G(v,u),\qquad \operatorname{rad}(G)=\min_{v\in V}e_G(v), \] and a center is a vertex attaining this minimum. The supplied source says that the ordinary Center problem is the all-one-profile case of its Weighted Center problem. However, it does not supply the definition of a profile or the formula for the weighted objective. Thus the ordinary objective above does not determine the intended weighted objective.

Source question, with unresolved specifications. Is there an almost-linear-time algorithm for the Weighted Center problem on median graphs of bounded cube dimension? Under the usual fixed-dimension reading, this asks for an algorithm for every fixed dimension bound $D$, valid for every admissible input graph with cube dimension at most $D$ and every admissible weight profile. The supplied record does not specify the admissible weights, the weighted objective, the permitted locations of a center, or the required output. Consequently, this is a statement of the source's algorithmic target rather than a fully specified computational problem. The finite graph and vertex-center conventions above describe the ordinary graph setting; their applicability to every part of the intended weighted problem requires confirmation. The meaning of almost-linear time, its input-size parameter, and its dependence on $D$ and weight encoding also remain unspecified.

Short English statement

The question asks whether Weighted Center can be computed in almost-linear time on median graphs when cube dimension is bounded by a fixed constant. The supplied record omits the definition of the weighted objective and several computational conventions, so a complete precise formulation requires further source clarification. Its open status is supplied dated curation, not an independently verified conclusion.

Sources

• Local problem registry, permanent UnsolvedMath ID $30006605$, title Weighted Centers on Bounded-Dimensional Median Graphs, source code catalogue entry. The supplied record identifies this as Open problem 1, proposed year 2026, in the Oberwolfach Reports Open Problems collection. No individual proposer is supplied.
• Median Geometry and Applications (2026), Oberwolfach Reports, DOI 10.4171/owr/2026/8, pp. 487--540. Supplied source and literature-source link, labeled Oberwolfach Report 8/2026: https://doi.org/10.4171/owr/2026/8.
• Chepoi et al., Diameter, radius and all eccentricities. Supplied literature-source link: https://arxiv.org/abs/2105.12150.
• Literature assessment dated 2026-08-22: the supplied curation labels the problem open and states that known results provide almost-linear algorithms for unweighted centers and restricted subclasses, without settling the weighted bounded-cube-dimension case. This is supplied dated curation derived from the OWR record, not independently verified literature or source checking; time-sensitive status and cited claims require independent verification.
• The registry labels the statement corrected_verified and says that only formula delimiters, notation, grammar, and typography were repaired while preserving mathematical content and scope. These are supplied editorial labels, not mathematical verification of this draft.