research
∙
08/29/2023
Approximate Monotone Local Search for Weighted Problems
In a recent work, Esmer et al. describe a simple method - Approximate Mo...
share
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...
research
∙
11/08/2022
Computing Square Colorings on Bounded-Treewidth and Planar Graphs
A square coloring of a graph G is a coloring of the square G^2 of G, tha...
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
∙
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/11/2020
Hitting Long Directed Cycles is Fixed-Parameter Tractable
In the Directed Long Cycle Hitting Set problem we are given a directed g...
research
∙
03/05/2020
Parameterized Algorithms for Generalizations of Directed Feedback Vertex Set
The Directed Feedback Vertex Set (DFVS) problem takes as input a directe...
research
∙
11/29/2019
Tight Bounds for Planar Strongly Connected Steiner Subgraph with Fixed Number of Terminals (and Extensions)
(see paper for full abstract) Given a vertex-weighted directed graph G...
research
∙
10/16/2018
Multi-budgeted directed cuts
We study multi-budgeted variants of the classic minimum cut problem and ...
research
∙
04/11/2018
Subexponential-time Algorithms for Maximum Independent Set in P_t-free and Broom-free Graphs
In algorithmic graph theory, a classic open question is to determine the...
research
∙
11/10/2017
