Deterministic Optimization of Top-$k$ Perfect-Matching Edges

Repeated top-k matching question: failure of a matroid-greedy interpretation

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.

A perfect matching is a set of disjoint edges covering every vertex exactly once. If its edge weights in nonincreasing order are $w_1\geq\cdots\geq w_t$, its top-$k$ objective is $\sum_{i=1}^kw_i$, with $0\leq k\leq t$. The input weights are finitely encoded, and polynomial time is measured in their binary length and the graph size.

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 report confirms that this is a duplicate extraction of the top-k perfect-matching question retained in OWR-8415356-025. No separate clean mathematical statement is supplied; this source ID preserves its provenance.

Related catalogue records: 30004914. 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.

It remains open if we can get a deterministic polynomial-time algorithm for this problem. In addition, the complexity of the problem (without restrictions on the edge-weights) remains open. Open problem: Perfect matching that maximizes the k-heaviest edges Ola Svensson [S2]

Source status.

The supplied catalogue labels this source record partially solved; 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-22.

Short English statement

The supplied fragment concerns deterministic Optimization of Top-k Perfect-Matching Edges. Its complete mathematical target is not recovered.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004915 (OWR-8415356-026). 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 Combinatorial Optimization $2022$, Oberwolfach Reports, DOI 10.4171/owr/2021/53, pp. 2893--2954 https://doi.org/10.4171/owr/2021/53.
• S3 Exact matching and top-k perfect matching https://arxiv.org/abs/2209.09661.
• S4 Restricted top-k matching algorithms https://arxiv.org/abs/2510.12552.
• Source-specific Oberwolfach Reports licences, including CC BY-SA 4.0 where applicable, are retained; see THIRD_PARTY_NOTICES.md.

Verbatim supplied catalogue question

It remains open if we can get a deterministic polynomial-time algorithm for this problem. In addition, the complexity of the problem (without restrictions on the edge-weights) remains open. Open problem: Perfect matching that maximizes the k-heaviest edges Ola Svensson

The original problem behind the trailing fragment

The primary source identifies this text as the continuation of the bipartite top-$k$ perfect-matching question retained in 30004914. It does not introduce a new independent problem. We test whether the source's extendable-edge-set formulation defines a matroid, which would justify a simple weight-greedy algorithm. It does not, as the following fully specified bipartite example shows.

The hereditary family and its failed exchange axiom.

Let a six-cycle have alternating edge sets $A=\{a_1,a_2,a_3\}$ and $B=\{b_1,b_2,b_3\}$. Its only perfect matchings are $A$ and $B$: the choice of which edge covers one vertex forces the next uncovered vertex's choice successively around the cycle. Therefore the family $\mathcal I$ of edge sets extendable to a perfect matching consists exactly of all subsets of $A$ and all subsets of $B$. It is hereditary, because a subset of a set contained in a perfect matching is still contained in that matching.

Take $I=\{a_1\}$ and $J=\{b_1,b_2\}$. Both belong to $\mathcal I$ and $|I|<|J|$. But adding either element of $J\setminus I$ to $I$ gives a set containing an edge of each alternating class, and neither perfect matching contains such a set. Thus no such addition lies in $\mathcal I$, violating the matroid augmentation axiom. This proof does not depend on whether the chosen two edges already share endpoints: sharing endpoints would also prevent extension, and the exact family description covers both possibilities.

The corresponding greedy optimization failure.

Give $a_1$ weight ten, $a_2,a_3$ weight zero, and every $b_i$ weight six. For $k=2$, a greedy procedure that repeatedly chooses the largest-weight edge preserving extendability first chooses $a_1$. It can then extend its selected set only within $A$, so its two-edge score is ten. The two-edge subset $\{b_1,b_2\}$ is extendable to $B$ and has score twelve. The best top-two perfect matching is $B$, also with score twelve, because the two available perfect matchings have scores ten and twelve. Hence a feasible-extension oracle does not by itself make descending-weight greedy exact.

The source's subset equivalence remains valid: the $k$ heaviest edges of any matching form an extendable $k$-set, and any extendable $k$-set has weight at most the top-$k$ total of a matching extending it. What fails is the extra exchange property needed to optimize that family by the matroid greedy theorem. Replacing extension tests by a matching algorithm does not repair the absent exchange axiom.

Audit and missing deterministic mechanism

The primary paragraph on printed page 2948 and its continuation were inspected. The audit kept the graph bipartite, enumerated all perfect matchings by the forcing argument, and distinguished an extendability decision procedure from weighted optimization over extendable sets. All numbers and matching choices were checked by hand; no solver or randomized algorithm was run. The example refutes this specific deterministic greedy route but provides no complexity lower bound or uniform polynomial algorithm for varying $k$. That original task remains unresolved under this duplicate source record.

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. The extendable-edge family is hereditary but not a matroid, and exact extension tests do not make greedy top-k optimization correct; the source deterministic question remains unresolved.

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 53/2021, Combinatorial Optimization, original question and surrounding discussion read from the primary PDF text on 11 October 2026. Historical statements are not a current-status survey. https://ems.press/content/serial-article-files/46931.

Final status

Unresolved in this attempt. The extendable-edge family is hereditary but not a matroid, and exact extension tests do not make greedy top-k optimization correct; the source deterministic question remains unresolved.

Top-k perfect matching: extendable subsets and a failed threshold minimax swap

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 perfect matching is a set of disjoint edges covering every vertex exactly once. If its edge weights in nonincreasing order are $w_1\geq\cdots\geq w_t$, its top-$k$ objective is $\sum_{i=1}^kw_i$, with $0\leq k\leq t$. The input weights are finitely encoded, and polynomial time is measured in their binary length and the graph size.

Statement recorded in the supplied source.

Given a weighted graph and an integer $k$, is there a deterministic polynomial-time algorithm that finds a perfect matching maximizing the total weight of its $k$ heaviest edges? [S2]

Scope qualification.

The question asks for a deterministic algorithm on general graphs, and does not restrict to bipartite graphs. If no perfect matching exists the algorithm must detect infeasibility.

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-22.

Short English statement

Find a perfect matching whose $k$ heaviest edges have the largest possible total weight.

Sources

• S1 Ulam AI and the UnsolvedMath Contributors, UnsolvedMath: A Curated Collection of Open Mathematics Problems, record 30004914 (OWR-8415356-025). 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 Combinatorial Optimization $2022$, Oberwolfach Reports, DOI 10.4171/owr/2021/53, pp. 2893--2954 https://doi.org/10.4171/owr/2021/53.
• S3 Combinatorial Optimization, Oberwolfach Reports 53/2021, primary report PDF https://ems.press/content/serial-article-files/46931. 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

Given a weighted graph and an integer $k$, is there a deterministic polynomial-time algorithm that finds a perfect matching maximizing the total weight of its $k$ heaviest edges?

The source graph class and the catalogue target

The primary passage explicitly starts with a bipartite graph, whereas the catalogue asks about weighted graphs generally. The identities and counterexample below apply to either class; the counterexample itself is bipartite. The explicit matching-feasibility routine used for the fixed-$k$ enumeration is justified for bipartite graphs. No unrestricted deterministic algorithm for varying $k$ is claimed.

Exact equivalence with extendable partial matchings.

Suppose a graph has a perfect matching with $t$ edges and $0\le k\le t$. Let $\mathcal R_k$ be the $k$-edge sets contained in some perfect matching. Then \[ \max_M\operatorname{top}_k(M)= \max_{R\in\mathcal R_k}\sum_{e\in R}w_e. \] For any perfect matching, its $k$ heaviest edges belong to $\mathcal R_k$, proving one inequality. Conversely any $R$ in that family extends to a matching $M$, and the sum of the largest $k$ weights in $M$ is at least the sum on that particular $k$-subset, proving the other. Negative weights and ties cause no change to these two comparisons. For $k=0$ both objectives are zero once feasibility is established.

For fixed $k$, enumerate all $k$-subsets of edges, discard those sharing an endpoint, delete the endpoints of each remaining set and test whether the residual graph has a perfect matching. This is exactly the extension test: its union with $R$ is perfect if and only if the residual matching is perfect. In a bipartite graph a maximum matching is found by repeatedly augmenting along alternating paths. Correctness follows because the symmetric difference with any larger matching has an augmenting path component; each search and the at most $|V|/2$ augmentations have polynomial cost. Hence enumeration takes $|E|^{O(k)}$ time and is polynomial for every fixed $k$. It is not a polynomial bound when $k$ is part of the input, since the exponent depends on $k$.

The threshold identity and the tempting illegal exchange.

For real numbers $a_1\ge\cdots\ge a_t$ and $1\le k<t$, \[ \sum_{i=1}^k a_i =\min_{\theta\in\mathbb R} \left(k\theta+\sum_{i=1}^t\max\{a_i-\theta,0\}\right). \] For any $\theta$, each of the first $k$ terms is at most $\theta+\max\{a_i-\theta,0\}$; summing and including the remaining nonnegative terms gives the upper-bound direction. If $a_{k+1}\le\theta\le a_k$, the first $k$ positive parts sum to $\sum_{i\le k}(a_i-\theta)$ and all remaining parts vanish, proving equality. This identity for one matching does not allow interchanging the maximum over matchings with this minimum over thresholds.

An exact bipartite minimax gap.

Take a six-cycle. It has exactly two perfect matchings, its two alternating triples: choosing the edge covering one vertex forces successive choices around the cycle, giving precisely these two. Give one triple weights $(10,0,0)$ and the other $(6,6,6)$, and set $k=2$. Their top-two values are ten and twelve, so the true optimum is twelve. For $0\le\theta\le6$ their threshold objectives are $10+\theta$ and $18-\theta$. The maximum is minimized at $\theta=4$ with value fourteen. For $\theta<0$ the second objective is $18-\theta>18$; for $6\le\theta\le10$ the first is $10+\theta\ge16$; and for $\theta\ge10$ both are $2\theta\ge20$. Consequently \[ \max_M\min_\theta\Phi(M,\theta)=12 \quad\hbox{but}\quad \min_\theta\max_M\Phi(M,\theta)=14. \] The inner maximization at fixed threshold is an ordinary weighted matching objective, but solving that family of objectives optimizes the displayed upper bound, not an equal reformulation of the original problem. This explicit gap blocks that proposed proof of a deterministic solution; it does not exclude other threshold-based algorithms with an additional argument.

Audit

The original top-$k$ passage on printed page 2948 was inspected. The audit corrected the source/catalogue graph-class discrepancy, retained binary-encoded unrestricted weights, and did not equate fixed-$k$ polynomial time with a uniform polynomial algorithm. The six-cycle calculation is exact hand enumeration of two matchings; no matching solver or random isolation procedure was run. Derandomization or another uniform deterministic optimization mechanism for varying $k$ remains missing in this attempt.

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. Exact extendable-subset equivalence and fixed-k bipartite enumeration do not give uniform polynomial time; a concrete minimax gap defeats the naive threshold interchange.

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 53/2021, Combinatorial Optimization, original question and surrounding discussion read from the primary PDF text on 11 October 2026. Historical statements are not a current-status survey. https://ems.press/content/serial-article-files/46931.

Final status

Unresolved in this attempt. Exact extendable-subset equivalence and fixed-k bipartite enumeration do not give uniform polynomial time; a concrete minimax gap defeats the naive threshold interchange.