Duplicate Bicriteria Spanning-Tree Enumeration

Repeated Pareto question: an output-polynomial algorithm on a complementary-cost block family

Definitions and mathematical statement

Shared notation.

Standard number systems are $\mathbb N,\mathbb Z,\mathbb Q,\mathbb R,\mathbb C$. Specialized notation and index ranges follow the cited source and the definitions below.

Output-polynomial time is polynomial in the input length plus the total encoded output length. A Pareto-optimal tree is distinct from its cost pair: different trees may have the same pair.

Record scope and qualifications.

The catalogue title is retained as metadata. Named certificates, contracts, bounds or frameworks in that title are not asserted as results of the original source extract. The supplied registry flags this extraction as unrecoverable. It is displayed as a literal source fragment; the definitions provide context rather than a replacement formal statement.

Source-record limitation: Source flags the statement as unrecoverable: The official Oberwolfach report was checked directly. This extraction repeats the same source problem as OWR-730-014 and is only a trailing repetition of the same source sentence.

Related catalogue records: 30000064. Separate source IDs are preserved for their provenance. The source text below is rendered literally where necessary; damaged formulas and composite extracts are not silently repaired into a new mathematical claim. The supplied catalogue marks this record as unrecoverable. Its extract and terminology are documented, but a complete original problem has not been reconstructed.

Statement recorded in the supplied source.

For constrained bicriteria minimum spanning tree, enumerate all Pareto-optimal solutions in time polynomial in the number of solutions. [S2]

Source status.

The supplied catalogue labels this source record open; that metadata was checked against the supplied snapshot on 2026-10-11. The label is preserved for provenance and is not an independent verification of present open status or mathematical correctness. The catalogue literature assessment is dated 2026-08-21.

Short English statement

The supplied fragment concerns duplicate Bicriteria Spanning-Tree Enumeration. Its complete mathematical target is not recovered.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30000065 (OWR-730-015). Catalogue curation and metadata: CC BY 4.0. The source extract is retained; definitions, English summaries and qualifications 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.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

For constrained bicriteria minimum spanning tree, enumerate all Pareto-optimal solutions in time polynomial in the number of solutions.

Duplicate provenance and chosen attempted route

This trailing record repeats the bicriteria enumeration question already represented by 30000064. It is retained as a separate source ID, not counted as a new independent problem. We attempt an exact dynamic program on a family where articulation blocks make local choices independent, and identify the structural step missing on arbitrary graphs.

An exact special family.

Take a chain of $k$ triangles, successive triangles sharing one articulation vertex, and positive integers $a_1,\ldots,a_k$. In block $i$ use edge cost pairs $(1,1+a_i),(1+a_i,1),(1,1)$. Every spanning tree uses exactly two edges per block: three make a cycle, fewer than two disconnect a vertex or the articulation chain, and any choice of two in every block is connected and acyclic by induction attaching a tree at one vertex. The choice omitting the $(1,1)$ edge has block pair $(2+a_i,2+a_i)$ and is dominated by either alternative, $(2,2+a_i)$ or $(2+a_i,2)$. Replacing it preserves a tree and improves a coordinate strictly because $a_i>0$. Thus all Pareto trees choose one of the latter two in every block.

Let $A=\sum_i a_i$ and let $\mathcal S$ be the set of subset sums of these integers. The distinct Pareto pairs are exactly \[ (2k+s,\ 2k+A-s),\qquad s\in\mathcal S. \] Each occurs by choosing the corresponding blocks, and distinct pairs have the same coordinate sum, so none dominates another. Every noncanonical tree is dominated by a canonical one by the replacement argument, proving completeness of this description.

Sparse dynamic programming with an output bound.

Set $S_0=\{0\}$ and recursively $S_i=S_{i-1}\cup(S_{i-1}+a_i)$, retaining for every sum one predecessor and whether block $i$ was chosen. Induction on $i$ proves that $S_i$ is exactly the set of sums obtainable from the first $i$ integers: every subset either excludes the last item or includes it and has a remaining predecessor sum. The predecessor records reconstruct a representative tree for each final sum. Because later items can all be omitted, $S_i\subseteq S_k$, so $|S_i|\le K=|S_k|$ at every step. Sorting and merging the two sorted lists constructs a next set using $O(K)$ additions/comparisons per step once the previous set is sorted. Each integer has at most $O(\log(A+1))$ bits. Thus the complete computation and reconstruction use a number of bit operations polynomial in the input length and $kK$, the representative-output size. This is output-polynomial for distinct pairs on this family, even when $A$ is numerically huge. It avoids a dense table of all integers through $A$.

If the requested output is every Pareto tree, all $2^k$ canonical choices must instead be listed, including choices with equal sums. Directly enumerating those choices and writing their $2k$ edges takes $O(k2^k)$ combinatorial work, polynomial in that larger output length. The two output conventions have separate valid algorithms for this special family.

The first generalization gap.

The recurrence relies on two facts: every partial choice extends independently through the remaining articulation blocks, and both costs are complementary functions of one subset sum. General spanning-tree choices can create cycles across proposed blocks and can merge different boundary components, so a state consisting only of a cost pair loses extension information. For example in a triangle, two selected edges already connect the endpoints of the third, forbidding it; in a path with the same two edge costs, an edge to a new vertex may still be required. Equal accumulated costs do not encode that connectivity difference. Extra connectivity states need a new output-sensitive bound, which is not supplied.

Audit

The repeated source sentence and its original surrounding bicriteria section on printed page 1533 were inspected. The audit checked positive $a_i$, dominance direction, equal subset sums and the monotonic bound on intermediate state counts. No subset-sum program or tree enumeration was executed. This is a completely proved restricted-family algorithm, not a new solution to general Pareto spanning-tree enumeration or an independent duplicate conjecture.

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. A complete output-polynomial algorithm works for the stated complementary-cost articulation family; general connectivity-state and frontier-size control remain missing.

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. A complete output-polynomial algorithm works for the stated complementary-cost articulation family; general connectivity-state and frontier-size control remain missing.