Parameterizing the Permanent: Genus, Apices, Minors, Evaluation Mod 2k

We identify and study relevant structural parameters for the problem PerfMatch of counting perfect matchings in a given input graph C. These generalize the well-known tractable planar case, and they include the genus of C, its apex number (the minimum number of vertices whose removal renders C planar), and its Hadwiger number (the size of a largest clique minor). To study these parameters, we first introduce the notion of combined matchgates, a general technique that bridges parameterized counting problems and the theory of so-called Holants and matchgates: Using combined matchgates, we can simulate certain nonexisting gadgets F as linear combinations of L = O(1) existing gadgets. If a graph C features k occurrences of F, we can then reduce C to t k graphs that feature only existing gadgets, thus enabling parameterized reductions. As applications of this technique, we simplify known 4 g n O(1) time algorithms for PerfMatch on graphs of genus g. Orthogonally to this, we show #W[1]-hardness of the permanent on k-apex graphs, implying its ⊕W[1]-hardness under the Hadwiger number. Additionally, we rule out n o(k/ log k) time algorithms under the counting exponential-time hypothesis #ETH. Finally, we use combined matchgates to prove $W[1]-hardness of evaluating the permanent modulo 2k, complementing an O(n 4k-3 ) time algorithm by Valiant and answering an open question of Bjϋrklund. We also obtain a lower bound of n Ω(k/ log k) under the parity version $ETH of the exponential-time hypothesis.

Authors

• Radu Curticapean
• Mingji Xia

Keywords

• Complexity theory
• Transmission line matrix methods
• Partitioning algorithms
• Computer science
• Polynomials
• Structural engineering
• Bipartite graph
• Lower Bound
• Linear Combination
• Perfect Match
• Problem Parameters
• Graph Features
• Counting Problem
• Multiple Edges
• Planar Graphs
• Combined Signature
• Class Of Graphs
• Hardness Results
• permanent
• perfect matchings
• parameterized counting complexity
• genus
• apex number
• graph minors
• Hadwiger number
• modular counting complexity
• Holant problem
• matchgates