Radu Curticapean

activity

20132026

most citedHomomorphisms Are a Good Basis for Counting Small Subgraphs

81 citations · 134 across the 18 of their papers we have counts for

collaborators

Showing 2025Show all

4 papers · 1 filter

cs.CC2025

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…

cs.CC2025

Monotone Bounded-Depth Complexity of Homomorphism Polynomials

C. S. Bhargav, Shiteng Chen, Radu Curticapean +1

For every fixed graph $H$ , it is known that homomorphism counts from $H$ and colorful $H$ -subgraph counts can be determined in $O (n^{t + 1})$ time on $n$ -vertex input graphs $G$ , whe…

cs.DS2025

Faster Convolutions: Yates and Strassen Revisited

Cornelius Brand, Radu Curticapean, Baitian Li +1

Given two vectors $u, v \in Q^{D}$ over a finite domain $D$ and a function $f : D \times D \to D$ , the convolution problem asks to compute the vector $w \in Q^{D}$ whose…

cs.CC2025

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 $G$ and an integer $k$ , this problem asks to count the number of induced $k$ -ver…