1 citations · 2 across the 2 of their papers we have counts for
5 papers
Parameterizing the Permanent: Hardness for -minor-free graphs
Radu Curticapean, Mingji Xia
In the 1960s, statistical physicists discovered a fascinating algorithm for counting perfect matchings in planar graphs. Valiant later showed that the same problem is #P-hard for g…
Modular counting of subgraphs: Matchings, matching-splittable graphs, and paths
Radu Curticapean, Holger Dell, Thore Husfeldt
We systematically investigate the complexity of counting subgraph patterns modulo fixed integers. For example, it is known that the parity of the number of -matchings can be det…
A full complexity dichotomy for immanant families
Radu Curticapean
Given an integer and an irreducible character of for some partition of , the immanant maps matri…
A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
Radu Curticapean, Nathan Lindzey, Jesper Nederlof
For even , the matchings connectivity matrix encodes which pairs of perfect matchings on vertices form a single cycle. Cygan et al. (STOC 2013) showed that th…
Homomorphisms Are a Good Basis for Counting Small Subgraphs
Radu Curticapean, Holger Dell, Dániel Marx
We introduce graph motif parameters, a class of graph parameters that depend only on the frequencies of constant-size induced subgraphs. Classical works by Lovász show that many in…