Hardness conjecture for bounded-size inversion approximation

From papers

Let p3p\geq 3 and k1k\geq 1 be integers. For a digraph DD, let sinvkp(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 p3p\geq 3 and every k1k\geq 1, no polynomial-time (1+ε)(1+\varepsilon)-approximation algorithm for sinvkp\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.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Florian Hörsch and Lucas Picasarri-Arrieta, “Increasing arc-connectivity by bounded- and fixed-size inversions”, arXiv:2604.22584 (2026).

Solutions 0

No solutions have been posted yet.