Weighted Min–Max Theorems for Disjoint Terminal Paths

Definitions and mathematical statement

Let $G=(V,E)$ be an undirected graph, let $S\subseteq V$ be its set of terminals, and let $w:\binom{S}{2}\to{\mathbb{N}}$, where $\binom{S}{2}=\{\{s,t\}:s,t\in S,\ s\ne t\}$. The supplied record does not specify whether $0\in{\mathbb{N}}$.

For a conventional interpretation of the optimization problem, assume that $G$ is finite. Interpret an $S$-path as a simple path with two distinct endpoints in $S$ and all internal vertices in $V\setminus S$. Write $s(P),t(P)$ for its endpoints. A family $\mathcal P$ of such paths is node-disjoint if $V(P)\cap V(Q)=\varnothing$ for every two distinct members $P,Q\in\mathcal P$, including their endpoints. Define \[ \nu_w(G,S)=\max_{\mathcal P}\sum_{P\in\mathcal P}w\left(\{s(P),t(P)\}\right), \] where the maximum ranges over all node-disjoint families of $S$-paths and the empty family has weight $0$. Finiteness and these path conventions are explicit interpretive assumptions; the supplied statement does not itself specify them.

Recorded question. For every such input $(G,S,w)$, does $\nu_w(G,S)$ admit a Mader-type min--max characterization, and can an optimal family be found in polynomial time?

Unresolved scope. This is a precise definition of the conventional maximization objective, but the intended theorem cannot be recovered completely from the supplied record. In particular, "Mader-type" does not specify the objects over which a minimum would be taken or their cost, and the input representation and intended polynomial-time bound are unspecified. The supplied literature assessment states that the extraction is truncated before the intended general weighted theorem is specified. Additional restrictions on weights or other hypotheses may therefore be missing. Its assertion that tree-distance weights are solvable is supplied background, without a precise definition or theorem here, and is not an independently verified conclusion of this draft.

Short English statement

The recorded question asks whether the greatest total endpoint-pair weight of vertex-disjoint terminal paths has a Mader-type min--max formula and a polynomial-time algorithm. Under explicitly stated conventional path assumptions, the objective is defined above. The intended weighted theorem remains incomplete because the supplied assessment reports a truncated extraction and leaves the minimum side and possible weight restrictions unspecified.

Sources

• Local registry: data/unsolvedmath/problems.json and the supplementary registry catalog/problems.json; supplied record for permanent UnsolvedMath ID $30001433$, source problem code catalogue entry, titled "Weighted Min--Max Theorems for Disjoint Terminal Paths," in the Oberwolfach Reports Open Problems collection. These are registry references, not a claim of independent file inspection.
• Supplied report provenance: Graph Theory (2010), Oberwolfach Reports, DOI 10.4171/owr/2010/11, pp. 521--580. https://doi.org/10.4171/owr/2010/11. The collection describes these reports as records of mathematical workshops and their open-problem discussions. The registry gives proposed year 2010 but names no individual proposer.
• Supplied literature reference: "Yamaguchi, weighted disjoint S-paths." https://doi.org/10.4230/LIPIcs.ISAAC.2016.63. No further bibliographic details or precise theorem are supplied.
• Literature assessment dated 2026-08-21: the supplied curation labels the problem open, reports that the extraction is truncated before specifying the intended general weighted theorem, and states that tree-distance weights are solvable while the full statement cannot be verified from this record. This is supplied dated curation, not an independently verified literature assessment. Its listed sources are the two references above.
• The registry separately labels the statement corrected_verified and reports that its mathematical content was checked against the official Oberwolfach report, with notation, context, and question form normalized without changing the source-level claim. This is a supplied verification assertion; it does not resolve the supplied truncation warning. No external source was visited for this draft.