81 citations · 134 across the 18 of their papers we have counts for
28 papers
A Dense Weisfeiler-Leman Algorithm for Deciding Bounded-Cliquewidth Homomorphism Indistinguishability
Radu Curticapean, Daniel Neuen, Amir Nikabadi +2
Two graphs and are homomorphism indistinguishable over a graph class if they admit the same number of homomorphisms from every graph in . A wide…
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…
Faster Convolutions: Yates and Strassen Revisited
Cornelius Brand, Radu Curticapean, Baitian Li +1
Given two vectors over a finite domain and a function , the convolution problem asks to compute the vector whose…
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…
Can You Link Up With Treewidth?
Radu Curticapean, Simon Döring, Daniel Neuen +1
In a fundamental paper in parameterized complexity theory, Marx [ToC '10] constructed -vertex graphs of maximum degree such that time algorithms for d…
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…
Fast Deterministic Chromatic Number under the Asymptotic Rank Conjecture
Andreas Björklund, Radu Curticapean, Thore Husfeldt +2
In this paper we further explore the recently discovered connection by Björklund and Kaski [STOC 2024] and Pratt [STOC 2024] between the asymptotic rank conjecture of Strassen [Pro…
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…
Determinants from homomorphisms
Radu Curticapean
We give a new combinatorial explanation for well-known relations between determinants and traces of matrix powers. Such relations can be used to obtain polynomial-time and poly-log…
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…
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…
Finding Detours is Fixed-parameter Tractable
Ivona Bezáková, Radu Curticapean, Holger Dell +1
We consider the following natural "above guarantee" parameterization of the classical Longest Path problem: For given vertices s and t of a graph G, and an integer k, the problem L…
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…