11 citations · 18 across the 4 of their papers we have counts for
4 papers
Count on CFI graphs for #P-hardness
Radu Curticapean
Given graphs and , possibly with vertex-colors, a homomorphism is a function that preserves colors and edges. Many interesting counting problems (e.g., subg…
Counting matchings with k unmatched vertices in planar graphs
Radu Curticapean
We consider the problem of counting matchings in planar graphs. While perfect matchings in planar graphs can be counted by a classical polynomial-time algorithm, the problem of cou…
Complexity of counting subgraphs: only the boundedness of the vertex-cover number counts
Radu Curticapean, Dániel Marx
For a class of graphs, #Sub is the counting problem that, given a graph and an arbitrary graph , asks for the number of subgraphs…
Counting perfect matchings in graphs that exclude a single-crossing minor
Radu Curticapean
A graph is single-crossing if it can be drawn in the plane with at most one crossing. For any single-crossing graph , we give an time algorithm for counting perfect…