Daniel Neuen

activity

20242026

collaborators

Showing cs.CCShow all

4 papers · 1 filter

cs.CC2025

Counting Small Induced Subgraphs: Hardness via Fourier Analysis

Radu Curticapean, Daniel Neuen

For a fixed graph property $I^¦$ and integer $k \geq 1$ , consider the problem of counting the induced $k$ -vertex subgraphs satisfying $I^¦$ in an input graph $G$ . This problem can be…

cs.CC2025

Treedepth Inapproximability and Exponential ETH Lower Bound

Ãdouard Bonnet, Daniel Neuen, Marek SokoÅowski

Treedepth is a central parameter to algorithmic graph theory. The current state-of-the-art in computing and approximating treedepth consists of a $2^{O (k^{2})} n$ -time exact algorith…

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 $(I^¦)$ for fixed graph properties $I^¦$ : Given a graph $G$ and an integer $k$ , this problem asks to count the number of induced $k$ -v…

cs.CC2025

Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part I: Algorithmic Results

Jacob Focke, DÃ¡niel Marx, Fionn Mc Inerney +4

We investigate how efficiently a well-studied family of domination-type problems can be solved on bounded-treewidth graphs. For sets $I ¨ , I ¨ $ of non-negative integers, a $(I ¨ , I ¨ )$ -s…