Bounded weakening for constrained invertibility
Fix a field $k$. A constrained invertibility problem of size $n$ is a pair $(P, Q)$ of $n \times n$ matrices with entries in $\{0, *\}$. It is feasible over $k$ if there are $A, B \in k^{n \times n}$ with $AB = I_n$ such that $A_{ij} = 0$ whenever $P_{ij} = 0$ and $B_{ij} = 0$ whenever $Q_{ij} = 0$; a star allows any entry, including zero. Let $G(P,Q)$ be the directed bipartite graph on $u_1, \ldots, u_n, v_1, \ldots, v_n$ with an edge $u_i \to v_j$ when $P_{ji} = *$ and an edge $v_j \to u_i$ when $Q_{ij} = *$, and let $d_G(x,y)$ be the length of a shortest directed path from $x$ to $y$ ($+\infty$ if there is none).
Constrained invertibility problems were introduced by Bjerkevik and Botnan, and used by them, and with Kerber, to prove that the interleaving distance between multiparameter persistence modules is NP-hard to compute and to approximate within a factor less than $3$. Bjerkevik and Botnan gave a feasible problem of size three that admits no solution in which $A$ is a permutation matrix, so $c = 1$ does not suffice below. Bjerkevik proved that, for each odd $c$, the condition below holds for every feasible problem if and only if any two $\epsilon$-interleaved pointwise finite-dimensional upset decomposable persistence modules admit a $c\epsilon$-matching.
Problem. Is there an odd integer $c \ge 1$, independent of $n$, $P$ and $Q$, such that every feasible problem admits a permutation $\sigma$ of $\{1, \ldots, n\}$ with $$d_G(u_i, v_{\sigma(i)}) \le c \quad\text{and}\quad d_G(v_{\sigma(i)}, u_i) \le c \qquad (1 \le i \le n)?$$ Equivalently, after adding every edge between the two parts that joins the ends of a directed path of length at most $c$ in $G(P,Q)$, the resulting problem is feasible with $A$ a permutation matrix and $B = A^{-1}$. The field is fixed; no uniformity in $k$ is required.
Source: Bjerkevik (2026), Conjecture 6.10 (arXiv 2023); the case c = 3 is a slight weakening of a conjecture in the appendix of his PhD thesis (2020).
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- CO — Combinatorics
- Secondary
- AT, RA
- Keywords
- AIM Open Applied Problems, constrained invertibility problems, interleaving distance, multiparameter persistence
References
@article{bjerkevik2026stabilizing,
author = {Bjerkevik, H{\aa}vard Bakke},
title = {Stabilizing decomposition of multiparameter persistence modules},
journal = {Found. Comput. Math.},
volume = {26},
number = {2},
year = {2026},
pages = {939--998},
doi = {10.1007/s10208-025-09695-w},
eprint = {2305.15550},
archivePrefix = {arXiv},
}
@phdthesis{bjerkevik2020thesis,
author = {Bjerkevik, H{\aa}vard Bakke},
title = {Stability and Complexity in Multi-Parameter Persistence},
school = {Norwegian University of Science and Technology (NTNU)},
year = {2020},
url = {https://hdl.handle.net/11250/2656497},
}
@inproceedings{bjerkevik2018complexity,
author = {Bjerkevik, H{\aa}vard Bakke and Botnan, Magnus Bakke},
title = {Computational complexity of the interleaving distance},
booktitle = {34th International Symposium on Computational Geometry ({SoCG} 2018)},
series = {LIPIcs},
volume = {99},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum f{\"u}r Informatik},
year = {2018},
pages = {13:1--13:15},
doi = {10.4230/LIPIcs.SoCG.2018.13},
eprint = {1712.04281},
archivePrefix = {arXiv},
}
@article{bjerkevik2020nphard,
author = {Bjerkevik, H{\aa}vard Bakke and Botnan, Magnus Bakke and Kerber, Michael},
title = {Computing the interleaving distance is {NP}-hard},
journal = {Found. Comput. Math.},
volume = {20},
number = {5},
year = {2020},
pages = {1237--1271},
doi = {10.1007/s10208-019-09442-y},
eprint = {1811.09165},
archivePrefix = {arXiv},
}
@misc{aim-constrained-invertibility-bounded-weakening,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Bounded weakening for constrained invertibility}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/24edaadc6bb272737d8da0745c662c992db07b22/problems/544-constrained-invertibility-bounded-weakening.md},
note = {Entry 544 at commit 24edaad, 2026-10-15},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00851, "Bounded weakening for constrained invertibility", clopen.solutions.