81 citations · 134 across the 18 of their papers we have counts for
18 papers · 1 filter
Counting Small Induced Subgraphs: Hardness of Symmetry-Based Properties
Radu Curticapean, Mingjun Liu
Jerrum and Meeks (TOCT, JCSS 2015) introduced the counting problems for fixed graph properties : Given an input graph and , count the -v…
Planar Perfect Matching Counting is as Hard as Determinants
Radu Curticapean, Jiaheng Wang
In the 1960s, Fisher, Kasteleyn and Temperley designed an ingenious algorithm for computing the partition function of the dimer model, or equivalently, for counting perfect matchin…
Beyond Bilinear Complexity: What Works and What Breaks with Many Modes?
Cornelius Brand, Radu Curticapean, Petteri Kaski +4
The complexity of bilinear maps (equivalently, of -mode tensors) has been studied extensively, most notably in the context of matrix multiplication. While circuit complexity and…
Which graph motif parameters count?
Markus Bläser, Radu Curticapean, Julian Dörfler +1
For a fixed graph H, the function #IndSub(H,*) maps graphs G to the count of induced H-copies in G; this function obviously "counts something" in that it has a combinatorial interp…
Monotone Bounded-Depth Complexity of Homomorphism Polynomials
C. S. Bhargav, Shiteng Chen, Radu Curticapean +1
For every fixed graph , it is known that homomorphism counts from and colorful -subgraph counts can be determined in time on -vertex input graphs , whe…
Counting Small Induced Subgraphs: Scorpions Are Easy but Not Trivial
Radu Curticapean, Simon Döring, Daniel Neuen
We consider the parameterized problem IndSub for fixed graph properties : Given a graph and an integer , this problem asks to count the number of induced -ver…
Counting Small Induced Subgraphs: Hardness via Fourier Analysis
Radu Curticapean, Daniel Neuen
For a fixed graph property and integer , consider the problem of counting the induced -vertex subgraphs satisfying in an input graph . This problem can be s…
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…
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 Fixed-Parameter Perspective on #BIS
Radu Curticapean, Holger Dell, Fedor Fomin +2
The problem of (approximately) counting the independent sets of a bipartite graph (#BIS) is the canonical approximate counting problem that is complete in the intermediate complexi…
Counting edge-injective homomorphisms and matchings on restricted graph classes
Radu Curticapean, Holger Dell, Marc Roth
We consider the -hard problem of counting all matchings with exactly edges in a given input graph ; we prove that it remains -hard on graph…
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…
Parity Separation: A Scientifically Proven Method for Permanent Weight Loss
Radu Curticapean
Given an edge-weighted graph G, let PerfMatch(G) denote the weighted sum over all perfect matchings M in G, weighting each matching M by the product of weights of edges in M. If G…
Parameterizing the Permanent: Genus, Apices, Minors, Evaluation mod 2^k
Radu Curticapean, Mingji Xia
We identify and study relevant structural parameters for the problem PerfMatch of counting perfect matchings in a given input graph . These generalize the well-known tractable p…
Block Interpolation: A Framework for Tight Exponential-Time Counting Complexity
Radu Curticapean
We devise a framework for proving tight lower bounds under the counting exponential-time hypothesis #ETH introduced by Dell et al. (ACM Transactions on Algorithms, 2014). Our frame…
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…