In inverse combinatorial optimization one asks how to minimally modify the weights of an optimization instance so that a prescribed solution becomes optimal. Yang and Zhang (2007), in their paper on partial inverse assignment problems under norms, contrasted the l∞l_\infty and l1l_1 formulations and observed that across normal (full-solution) inverse problems no separation between the two norms in the strongly polynomial sense is known — the prominent open case being the inverse maximum-weight perfect matching problem in general (non-bipartite) graphs, for which Liu and Zhang (2003) gave a strongly polynomial algorithm under l∞l_\infty but only an ellipsoid-based, weakly polynomial algorithm under l1l_1. The precise open question: does the inverse maximum-weight perfect matching problem in general graphs under the l1l_1 norm admit a strongly polynomial-time algorithm, one whose arithmetic-operation count is polynomial in the graph size and independent of the bit-length of the weights?

Background

In inverse combinatorial optimization, one is given an instance of a combinatorial optimization problem together with a prescribed feasible solution, and the task is to modify the numerical data (typically edge or element weights) as little as possible so that the prescribed solution becomes optimal. The modification cost is measured by a norm on the weight-change vector: the l∞l_\infty norm max⁡e∣w∗(e)−w(e)∣\max_e|w^*(e)-w(e)| (largest single change) or the l1l_1 norm ∑e∣w∗(e)−w(e)∣\sum_e|w^*(e)-w(e)| (total change). For many polynomially solvable network problems — shortest path, minimum spanning tree, bipartite assignment — the inverse problem under both norms can be reformulated as a linear program or a network-flow problem and is solvable in strongly polynomial time, meaning by an algorithm whose number of arithmetic operations is bounded by a polynomial in the combinatorial size of the instance (number of vertices and edges) and does not depend on the number of bits needed to represent the weights (Ahuja and Orlin, 2001; Heuberger, 2004). This is a strictly stronger guarantee than weakly polynomial methods such as the ellipsoid method, whose running time grows with the bit-length of the input numbers.

The assignment problem — finding a minimum- or maximum-weight perfect matching in a bipartite graph, where a perfect matching is a set of edges covering every vertex exactly once — is the classical bipartite case, and its inverse versions under both norms reduce to minimum-cost flow computations and are strongly polynomial. The non-bipartite case is structurally harder: by Edmonds' matching polytope theorem, a linear-programming description of perfect matchings in a general graph requires exponentially many blossom inequalities — one inequality for each odd-cardinality set of vertices. Liu and Zhang (2003) studied the inverse maximum-weight perfect matching problem in general (non-bipartite) graphs: given edge weights ww and a target perfect matching M∗M^*, find weights w∗w^* under which M∗M^* is a maximum-weight perfect matching, minimizing the norm of w∗−ww^*-w. They proved that the l∞l_\infty version reduces to a maximum-mean alternating-cycle problem (an alternating cycle is a cycle whose edges alternate between the prescribed matching M∗M^* and the remaining edges; the symmetric difference of two perfect matchings always decomposes into such cycles), solvable in strongly polynomial time by an ascending algorithm — one that monotonically raises a scalar parameter until the optimum is reached — but for the l1l_1 version they obtained only an ellipsoid-based, weakly polynomial algorithm.

A parallel line concerns partial inverse problems, where only part of a solution is prescribed: modify weights minimally so that some optimal solution extends the given partial solution. Yang and Zhang (2007) proved that the partial inverse assignment problem under the l1l_1 norm, with no bounds on the modified weights, is solvable in strongly polynomial time O(n3)O(n^3) via a two-step reduction — first find a minimum-cost full completion of the partial assignment, then reconstruct minimal weight changes from linear-programming duality — and extended this to 0–1 linear programs with totally unimodular constraint matrices (totally unimodular: every square subdeterminant equals 0 or ±1\pm 1, so all extreme points of the polyhedron are integral). In their closing discussion they contrasted the two norms: across normal (full-solution) inverse problems no example is known that separates the l1l_1 and l∞l_\infty formulations in the strongly polynomial sense, and the inverse maximum-weight perfect matching problem under l1l_1 stands out as the case still lacking a strongly polynomial algorithm; they also asked which further partial inverse problems are polynomial under l1l_1, and noted that with bound constraints on the weight changes partial inverse assignment is NP-hard (Yang, 2001).

Problem Statement

Does the inverse maximum-weight perfect matching problem in general (non-bipartite) graphs under the l1l_1 norm admit a strongly polynomial-time algorithm?

Formally: given a graph G=(V,E)G=(V,E) with real edge weights w:E→Rw:E\to\mathbb{R} and a prescribed perfect matching M∗⊆EM^*\subseteq E, the problem asks for weights w∗w^* minimizing

∑e∈E∣w∗(e)−w(e)∣\sum_{e\in E}|w^*(e)-w(e)|

subject to M∗M^* being a maximum-weight perfect matching of GG under w∗w^*. The question is whether this can be computed by an algorithm whose number of arithmetic operations is bounded by a polynomial in ∣V∣|V| and ∣E∣|E| alone — with no dependence on the bit-length or magnitude of the input weights — matching the status of the l∞l_\infty version (Liu and Zhang's strongly polynomial ascending algorithm for the maximum-mean alternating-cycle problem) and of the bipartite assignment case (strongly polynomial via minimum-cost flow).

A reduction of the problem to a problem already known to be solvable in strongly polynomial time, together with a proof of equivalence, implies a strongly polynomial algorithm for the original problem, whereas a polynomial-size reformulation whose known solvers are not themselves strongly polynomial — for instance, one solvable only by the ellipsoid method or otherwise with bit-length dependence — yields only a weakly polynomial algorithm for the original problem.

This problem is the open core of the question raised by Yang and Zhang (2007); the other two directions they raised lie outside it. The bounded-weight extension was settled negatively in general by the NP-hardness of Yang (2001), and the partial-inverse l1l_1 landscape has since been substantially mapped.

References

  1. Xiaoguang Yang, Jianzhong Zhang (2007). Partial inverse assignment problems under norm. Operations Research Letters 35(1):23–28. DOI: 10.1016/j.orl.2005.12.003. URL: https://doi.org/10.1016/j.orl.2005.12.003
  2. Zhenhong Liu, Jianzhong Zhang (2003). On inverse problems of optimum perfect matching. Journal of Combinatorial Optimization 7:215–228. DOI: 10.1023/A:1027305419461. URL: https://doi.org/10.1023/A:1027305419461
  3. Xiaoguang Yang (2001). Complexity of partial inverse assignment problem and partial inverse cut problem. RAIRO Operations Research 35:117–126. DOI: 10.1051/ro:2001106. URL: https://doi.org/10.1051/ro:2001106
  4. Ravindra K. Ahuja, James B. Orlin (2001). Inverse optimization. Operations Research 49(5):771–783. DOI: 10.1287/opre.49.5.771.10607. URL: https://doi.org/10.1287/opre.49.5.771.10607
  5. Clemens Heuberger (2004). Inverse combinatorial optimization: A survey on problems, methods, and results. Journal of Combinatorial Optimization 8:329–361. DOI: 10.1023/B:JOCO.0000038914.26975.9b. URL: https://doi.org/10.1023/B:JOCO.0000038914.26975.9b
  6. Longcheng Liu, Enyu Yao (2013). Weighted inverse maximum perfect matching problems under the Hamming distance. Journal of Global Optimization 55:549–557. DOI: 10.1007/s10898-012-9901-8. URL: https://doi.org/10.1007/s10898-012-9901-8
  7. Qin Wang, Tianyu Yang, Longshu Wu (2022). General restricted inverse assignment problems under l1l_1 and l∞l_\infty norms. Journal of Combinatorial Optimization 44:2040–2055. DOI: 10.1007/s10878-020-00577-1. URL: https://doi.org/10.1007/s10878-020-00577-1
  8. Kristóf Bérczi, Lydia Mirabel Mendoza-Cadena, Kitti Varga (2023). Inverse optimization problems with multiple weight functions. Discrete Applied Mathematics 327:134–147. DOI: 10.1016/j.dam.2022.12.004. URL: https://doi.org/10.1016/j.dam.2022.12.004
  9. Eva Ley, Maximilian Merkert (2025). Solution methods for partial inverse combinatorial optimization problems in which weights can only be increased. Journal of Global Optimization 93:263–298. DOI: 10.1007/s10898-025-01529-x. URL: https://doi.org/10.1007/s10898-025-01529-x
  10. Kristóf Bérczi, Mirabel Mendoza-Cadena, José Soto (2025). Subset-constrained inverse matroid optimization. arXiv:2507.00930. URL: https://arxiv.org/abs/2507.00930
  11. Timothy C. Y. Chan, Rafid Mahmood, Ian Yihang Zhu (2025). Inverse optimization: Theory and applications. Operations Research 73:1046–1074. DOI: 10.1287/opre.2022.0382. URL: https://doi.org/10.1287/opre.2022.0382
  12. Sara Ahmadian, Umang Bhaskar, Laura Sanità, Chaitanya Swamy (2018). Algorithms for inverse optimization problems. In 26th Annual European Symposium on Algorithms (ESA 2018), LIPIcs 112, 1:1–1:14. DOI: 10.4230/LIPIcs.ESA.2018.1. URL: https://doi.org/10.4230/LIPIcs.ESA.2018.1
  13. Huiling Li (2024). Clustering integrated fusion model based on the maximum matching problem. Journal of Combinatorial Mathematics and Combinatorial Computing 120:241–251. DOI: 10.61091/jcmcc120-21. URL: https://doi.org/10.61091/jcmcc120-21