Hardness conjecture for bounded-size inversion approximation

Less than 1 year old · traced to

Let p≥3p\geq 3 and k≥1k\geq 1 be integers. For a digraph DD, let sinv⁡k≤p(D)\operatorname{sinv}_{k}^{\leq p}(D) denote the optimization problem of making DD kk-arc-strong using inversions of size at most pp.

Bounded-size inversion approximation hardness conjecture. There exists ε>0\varepsilon>0 such that, unless P=NPP=NP, for every p≥3p\geq 3 and every k≥1k\geq 1, no polynomial-time (1+ε)(1+\varepsilon)-approximation algorithm for sinv⁡k≤p\operatorname{sinv}_{k}^{\leq p} 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

Never refreshed

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.