Offer 01€110 main targetDanupon Nanongkai
Personal offerThe official page reserves each cash prize for the first solver. Resolve either side of the main query-complexity target. The current listing expires in 2034.
01
The problem
Given a hidden directed unweighted graph where cut(S) returns the number of edges leaving S, either give an O(|V|^1.999)-query algorithm for s–t reachability or rule out O(|V|^1.001) queries; a smaller sub-bounty asks for any improvement below O(|V|²/log n).
Open since2024reward first offered
Last checked2026.07.27Catalog verification
02
Reward offers
Offer 02€5 improvement targetDanupon Nanongkai
Personal offerImprove the O(|V|²/log n) cut-query upper bound, for example to O(|V|²/(log n log log n)). This is a sub-bounty attached to the same reachability problem.
03