Paper Info
Title
The Precise Complexity of Finding Rainbow Even Matchings.
Abstract
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), ... , p(g), perfect matching M is Rainbow Even Matching (REM) if vertical bar M boolean AND p(i)vertical bar is even for each i = 1, ... , g. A straightforward algorithm finds a REM or asserts that no REM exists in 2(g) x 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.
Year
DOI
Venue
2019
10.1007/978-3-030-21363-3_16
ALGEBRAIC INFORMATICS, CAI 2019
Keywords
Field
DocType
Matching,Max cut,Exponential time hypothesis,Ising partition function
Discrete mathematics,Disjoint sets,Vertex (geometry),Computer science,Curse of dimensionality,Matching (graph theory),Conjecture,Planar graph,Maximum cut,Exponential time hypothesis
Conference
Volume
ISSN
Citations 
11545
0302-9743
0
PageRank 
References 
Authors
0.34
0
1
Name
Order
Citations
PageRank
Martin Loebl115228.66