exact_matching_parity (569B)
1 # Exact matching parity 2 3 - in [bipartite_graphs], can decide in [PTIME] whether there is a [perfect_matching] with an even number of red edges 4 - proof in [datta2010perfect] 5 - generalization to [maximum_matching] 6 - https://cstheory.stackexchange.com/a/41357 7 - unknown for other moduli? 8 - unknown for non-bipartite graphs? 9 - for general graphs and constant number of colors it can be done in [PTIME] 10 - [RP] algorithm from [mulmuley1987matching] 11 - cf [marx2004list] 12 - https://cstheory.stackexchange.com/a/41343 13 14 Up: [matching_variants], [exact_matching]