Hardness conjecture for bounded-size inversion approximation
Let and be integers. For a digraph , let denote the optimization problem of making -arc-strong using inversions of size at most .
Bounded-size inversion approximation hardness conjecture. There exists such that, unless , for every and every , no polynomial-time -approximation algorithm for in digraphs exists.
The conjecture asserts that increasing the allowed inversion size does not make the approximation problem easier. It is presented as an open conjecture in the source.
References
Primary source
Florian Hörsch and Lucas Picasarri-Arrieta, “Increasing arc-connectivity by bounded- and fixed-size inversions”, arXiv:2604.22584 (2026).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.