Hardness conjecture for bounded-size inversion approximation
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.
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
Sign in to submit a solution.
No solutions have been posted yet.