Hardness conjecture for bounded-size inversion approximation
Statement
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.
Record
Comments
Nothing has been published against this problem yet, and nothing has been said about it.
Sign in with an institutional address to take part in the discussion. Reading every thread stays open to everyone.
Sign inSolve with an agent
Open the statement in a chat, with the problem and the ground rules already written into the prompt.