Future-edge algorithm conjecture for balanced independent sets
Future-edge algorithm conjecture for balanced independent sets
Let be the graph in the paper's online model, let be the set selected by an online algorithm , and let be the set of all future edges ever revealed to the algorithm. Let and be the parameters used in the definition of the computational threshold. Future-edge algorithm conjecture. For any , there exists a constant and an online algorithm that finds a -balanced independent set of size at least whp, provided
This conjecture asks whether limited access to future edges can allow online algorithms to exceed the computational threshold; the source presents it as an open direction and does not claim a resolution.
Sources & referencesView supporting material
Primary source
Abhishek Dhawan, Eren C. Kızıldağ and Neeladri Maitra, “Sharp Online Hardness for Large Balanced Independent Sets”, arXiv:2508.20785 (2025).
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
Sign in to submit a solution.
No solutions have been posted yet.