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
∙
09/04/2022
Computing Generalized Convolutions Faster Than Brute Force
In this paper, we consider a general notion of convolution. Let D be a f...
research
∙
08/04/2022
Domination and Cut Problems on Chordal Graphs with Bounded Leafage
The leafage of a chordal graph G is the minimum integer l such that G ca...
research
∙
05/20/2022
Parameterized Complexity of Weighted Multicut in Trees
The Edge Multicut problem is a classical cut problem where given an undi...
research
∙
10/18/2021
Anti-Factor is FPT Parameterized by Treewidth and List Size (but Counting is Hard)
In the general AntiFactor problem, a graph G is given with a set X_v⊆ℕ o...
research
∙
05/19/2021
Degrees and Gaps: Tight Complexity Results of General Factor Problems Parameterized by Treewidth and Cutwidth
For the General Factor problem we are given an undirected graph G and fo...
research
∙
02/25/2021
Subcubic Certificates for CFL Reachability
Many problems in interprocedural program analysis can be modeled as the ...
research
∙
08/06/2020