The Precise Complexity of Finding Rainbow Even Matchings

A progress in complexity lower bounds might be achieved by studying problems where a very precise complexity is conjectured. In this note we propose one such problem: Given a planar graph on n vertices and disjoint pairs of its edges \(p_1, \ldots , p_g\), perfect matching M is Rainbow Even Matching (REM) if \(|M\cap p_i|\) is even for each \(i= 1, \ldots , g\). A straightforward algorithm finds a REM or asserts that no REM exists in \(2^g\times \mathrm {poly}(n)\) steps and we conjecture that no deterministic or randomised algorithm has complexity asymptotically smaller than \(2^g\). Our motivation is also to pinpoint the curse of dimensionality of the Max-Cut problem for graphs embedded into orientable surfaces: a basic problem of statistical physics.