Maximum weight k-element subsets of perfect matchings

Definitions and mathematical statement

Let $G=(U\sqcup W,E)$ be a finite bipartite graph with $|U|=|W|=n$, rational edge weights $w:E\to\mathbb Q$, and an integer $0\le k\le n$. A matching is an edge set with no shared endpoints. It is extendable when it is contained in some perfect matching of $G$.

Find a deterministic polynomial-time algorithm that computes \[ \max\left\{\sum_{e\in F}w(e):|F|=k,\quad F\subseteq M\text{ for a perfect matching }M\right\} \] and returns an optimal $F$ together with an extension $M$, or reports that no feasible solution exists. Polynomial time is measured in the graph size and binary encoding lengths of the weights and $k$.

The objective charges only the $k$ selected edges of $F$, not all edges in the perfect extension. Hence maximizing the weight of an entire perfect matching and then discarding edges does not immediately solve the stated problem. Similarly, an unconstrained optimum among $k$-edge matchings may fail to extend at all. The extension can depend on the chosen $F$ and is not specified in advance. The condition is existential for this particular selected matching; the graph need not have the stronger property that every $k$-edge matching is extendable.

Short English statement

Can one efficiently find the heaviest $k$ edges that form a matching extendable to a perfect matching of a bipartite graph?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3000054 (AMR-029-0054), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Egres Open - List of open problems, Open-problem page: Maximum weight k-element subsets of perfect matchings. Original source indexed by AMR-029-0054. https://oldlemon.cs.elte.hu/egres/open/List_of_open_problems.
• S3 EGRES Open, Maximum weight k-element subsets of perfect matchings. Individual source page and explanatory remarks. https://lemon.cs.elte.hu/egres/open/Maximum_weight_k-element_subsets_of_perfect_matchings.