research
∙
09/15/2023
On Induced Versions of Menger's Theorem on Sparse Graphs
Let A and B be sets of vertices in a graph G. Menger's theorem states th...
share
research
∙
08/30/2023
SharpSAT-TD in Model Counting Competitions 2021-2023
We describe SharpSAT-TD, our submission to the unweighted and weighted t...
research
∙
08/09/2023
Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition
A graph G contains a graph H as an induced minor if H can be obtained fr...
research
∙
07/03/2023
Polynomial-time Approximation of Independent Set Parameterized by Treewidth
We prove the following result about approximating the maximum independen...
research
∙
05/03/2023
Computing paths of large rank in planar frameworks deterministically
A framework consists of an undirected graph G and a matroid M whose elem...
research
∙
05/02/2023
Two-sets cut-uncut on planar graphs
We study the following Two-Sets Cut-Uncut problem on planar graphs. Ther...
research
∙
04/04/2023
Dynamic treewidth
We present a data structure that for a dynamic graph G that is updated b...
research
∙
02/21/2023
New Width Parameters for Independent Set: One-sided-mim-width and Neighbor-depth
We study the tractability of the maximum independent set problem from th...
research
∙
11/14/2022
An Improved Parameterized Algorithm for Treewidth
We give an algorithm that takes as input an n-vertex graph G and an inte...
research
∙
11/09/2022
Shortest Cycles With Monotone Submodular Costs
We introduce the following submodular generalization of the Shortest Cyc...
research
∙
10/05/2022
Tight Lower Bounds for Problems Parameterized by Rank-width
We show that there is no 2^o(k^2) n^O(1) time algorithm for Independent ...
research
∙
07/20/2022
Computing Tree Decompositions with Small Independence Number
The independence number of a tree decomposition is the maximum of the in...
research
∙
07/15/2022
Fixed-Parameter Tractability of Maximum Colored Path and Beyond
We introduce a general method for obtaining fixed-parameter algorithms f...
research
∙
03/24/2022
Grid Induced Minor Theorem for Graphs of Small Degree
A graph H is an induced minor of a graph G if H can be obtained from G b...
research
∙
11/05/2021
Fast FPT-Approximation of Branchwidth
Branchwidth determines how graphs, and more generally, arbitrary connect...
research
∙
04/15/2021
A Single-Exponential Time 2-Approximation Algorithm for Treewidth
We give an algorithm, that given an n-vertex graph G and an integer k, i...
research
∙
02/13/2021
Lower Bounds on Dynamic Programming for Maximum Weight Independent Set
We prove lower bounds on pure dynamic programming algorithms for maximum...
research
∙
12/16/2020
Listing Small Minimal Separators of a Graph
Let G be a graph and a,b vertices of G. A minimal a,b-separator of G is ...
research
∙
11/23/2020
Tight Bounds for Potential Maximal Cliques Parameterized by Vertex Cover
We show that a graph with n vertices and vertex cover of size k has at m...
research
∙
06/12/2020
SMS in PACE 2020
We describe SMS, our submission to the exact treedepth track of PACE 202...
research
∙
12/23/2019
