An FPAS for Constrained Bicriteria Spanning Trees

Constrained spanning trees: a scalarization obstruction and a conditional scaling route

Definitions and mathematical statement

Shared notation.

Standard number systems are denoted by $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$; index ranges, computational models and specialized notation follow the cited problem source and the definitions below.

A PTAS has approximation ratio $1+\varepsilon$ for minimization (or $1-\varepsilon$ for maximization), with polynomial runtime for each fixed $\varepsilon>0$. A fully polynomial scheme is polynomial also in $\varepsilon^{-1}$.

In a bicriteria minimization problem each feasible solution has two costs. A cost pair is Pareto-optimal if no feasible pair is no larger in both coordinates and strictly smaller in one.

A spanning tree of a connected finite graph is an acyclic connected subgraph containing every vertex. Its cost is the sum of its edge costs.

Statement recorded in the supplied source.

Does the constrained bicriteria minimum spanning-tree problem admit a fully polynomial approximation scheme? [S2]

Scope qualification.

The constrained objective, budget constraint, and permitted budget violation are those of the report; bicriteria budget violation is not silently permitted.

Source status.

The supplied catalogue labels this record partially solved. Its source-status metadata was checked against the supplied snapshot on 2026-10-11. This import does not independently establish current open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

Decide whether constrained spanning-tree optimization with two costs permits an approximation scheme polynomial in both input size and inverse accuracy.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30000063 (OWR-730-013). Catalogue curation and metadata: CC BY 4.0. The supplied source question is retained; definitions and the English summary are editorial additions. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Approximation Algorithms for NP-Hard Problems $2005$, Oberwolfach Reports, DOI 10.4171/owr/2004/28, pp. 1461--1540 https://doi.org/10.4171/owr/2004/28.
• S3 fully polynomial bicriteria approximation scheme https://doi.org/10.1016/j.orl.2003.06.003.
• S4 PTAS for constrained minimum spanning tree https://doi.org/10.1137/S0097539703426775. Underlying Oberwolfach Reports material retains its source-specific licence, including CC BY-SA 4.0 where applicable; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

Does the constrained bicriteria minimum spanning-tree problem admit a fully polynomial approximation scheme?

Exact budget is part of the target

The original constrained problem minimizes total weight under an upper bound on a second cost. A fully polynomial scheme must keep that budget exact; allowing a proportional budget violation changes the problem. We test a Lagrange-multiplier route and then spell out the exact oracle that a standard scaling argument would need.

A budget-optimal tree missed by every scalarization.

Take a triangle whose three edges have $(\hbox{cost},\hbox{weight})$ pairs $(6,0),(2,2),(0,6)$. Its three spanning trees have pairs \[ (8,2),\qquad(6,6),\qquad(2,8). \] They are all Pareto optimal because sorting by cost reverses the strict weight order. With cost budget six the optimum weight is six, attained by the middle tree. Yet that tree never minimizes $\hbox{weight}+\lambda\,\hbox{cost}$ for any $\lambda\ge0$. Beating the $(8,2)$ tree would require $6+6\lambda\le2+8\lambda$, or $\lambda\ge2$; beating the $(2,8)$ tree would require $6+6\lambda\le8+2\lambda$, or $\lambda\le1/2$. These requirements are inconsistent, even allowing ties. Thus enumerating ordinary MSTs under nonnegative scalarized costs can miss the exact-budget optimum. Selecting the best feasible tree among those supported optima gives weight eight here, so cannot prove any ratio below $4/3$ on this instance. This does not exclude algorithms using more than scalarization.

A correct conditional rounding calculation.

Let a graph have $n\ge2$ vertices and nonnegative weights $w_e$. Fix $\varepsilon>0$ and suppose a positive number $L\le\operatorname{OPT}$ is available. Set $K=\varepsilon L/(n-1)$ and $\widetilde w_e=\lfloor w_e/K\rfloor$. If an oracle returns an exact-budget feasible tree $T$ minimizing the rounded total, and $T^*$ is an original optimum, then \[ w(T)<K\widetilde w(T)+(n-1)K \le K\widetilde w(T^*)+(n-1)K \le\operatorname{OPT}+\varepsilon L \le(1+\varepsilon)\operatorname{OPT}. \] Every tree has exactly $n-1$ edges, and each rounding error lies in $[0,K)$, proving the first and third inequalities; the middle one is the oracle's optimality. The cost constraint is never rounded, so its exact feasibility is retained. Zero optimum requires a separate zero-weight feasibility check because $K=0$ is invalid.

The missing step is precisely that exact-budget rounded-weight oracle with time polynomial in the input and a suitable rounded-weight range. Ordinary minimum spanning tree does not supply it, as the triangle proves. Merely writing the scaling inequalities is not a fully polynomial algorithm, and a pseudopolynomial loop over a large binary-encoded budget is not polynomial in its input length.

Why rounding the budget instead is unsafe.

For any scale $K>0$, choose $0<\delta<K$ and consider a single required edge of cost $B+\delta$ with $B$ an integer multiple of $K$. Rounding its cost down to a multiple of $K$ makes it cost $B$, apparently feasible, whereas no tree satisfies the original budget $B$. Thus floor rounding of cost, unlike the objective rounding above, can manufacture feasibility. An algorithm must either retain exact costs or prove a different sound repair.

Audit

Problem 1 in the primary bicriteria section on printed page 1533 was inspected. The audit checked which coordinate is the constraint, both comparisons in the unsupported-tree example, zero optimum and input bit length. All arguments are exact and no spanning-tree solver was run. The conditional scaling calculation is standard material; no new oracle, fully polynomial scheme or hardness theorem is claimed.

Process and contributions

Mathematics and model-assisted adversarial self-audit: OpenAI gpt-6-astra, ultra reasoning, as dispatched for this research batch; exact serving revision not exposed. Codex (GPT-6; exact serving revision not exposed) materially assisted with orchestration and format review. No human mathematical authorship, mathematical edits, or independent human proof checking is asserted. Contribution prompt A was applied to the full definition and supplied source row, then prompt B was applied adversarially to the derived results. The item-specific audit above records the scope checks and rejected extrapolations. Local assembly and structural checks do not establish mathematical correctness. The source catalogue status is preserved in TOP_PROBLEM and is separate from this attempt status.

Integration review.

Codex (GPT-6; exact serving revision not exposed) reviewed the written arguments and expanded layout and source-reference wrappers. Repository metadata and the production web renderer were checked using Python 3.13 and JavaScript with MathJax 3.2.2. This model-assisted review is not independent human proof verification; no PDF compilation or formal proof checking is asserted.

Completion Estimate

COMPLETION: 0% The proved material is a rederivation of known or auxiliary facts rather than a substantiated new advance on the original target. Scalarization misses an exact-budget optimum, and the valid scaling argument requires an exact constrained oracle not constructed here.

References

The complete original Sources subsection above is retained, including catalogue attribution and licence notices. The additional list records primary sources actually consulted for this attempt on 11 October 2026; uncited source links reproduced above were not all rechecked.

• Oberwolfach Report 28/2004, Approximation Algorithms for NP-Hard Problems, original question and surrounding discussion read from the cached primary PDF text on 11 October 2026. Historical statements are not a current-status survey. https://doi.org/10.4171/owr/2004/28.

Final status

Unresolved in this attempt. Scalarization misses an exact-budget optimum, and the valid scaling argument requires an exact constrained oracle not constructed here.