research
∙
05/26/2023
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs Part II: Hardness Results
For a well-studied family of domination-type problems, in bounded-treewi...
share
research
∙
11/08/2022
Tight Complexity Bounds for Counting Generalized Dominating Sets in Bounded-Treewidth Graphs
We investigate how efficiently a well-studied family of domination-type ...
research
∙
10/19/2022
List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
The goal of this paper is to investigate a family of optimization proble...
research
∙
11/03/2021
Counting Small Induced Subgraphs with Hereditary Properties
We study the computational complexity of the problem #IndSub(Φ) of count...
research
∙
07/14/2021
Counting list homomorphisms from graphs of bounded treewidth: tight complexity bounds
The goal of this work is to give precise bounds on the counting complexi...
research
∙
03/23/2021
Approximately Counting Answers to Conjunctive Queries with Disequalities and Negations
We study the complexity of approximating the number of answers to a smal...
research
∙
06/30/2020
Counting Homomorphisms to K_4-minor-free Graphs, modulo 2
We study the problem of computing the parity of the number of homomorphi...
research
∙
07/04/2019
The Complexity of Approximately Counting Retractions to Square-Free Graphs
A retraction is a homomorphism from a graph G to an induced subgraph H o...
research
∙
07/02/2018