research
∙
08/03/2023
Another Hamiltonian Cycle in Bipartite Pfaffian Graphs
We present a linear-time algorithm that, given as input (i) a bipartite ...
share
research
∙
07/03/2023
Polynomial-time Approximation of Independent Set Parameterized by Treewidth
We prove the following result about approximating the maximum independen...
research
∙
07/03/2023
A Fine-Grained Classification of the Complexity of Evaluating the Tutte Polynomial on Integer Points Parameterized by Treewidth and Cutwidth
We give a fine-grained classification of evaluating the Tutte polynomial...
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
∙
08/04/2022
Makespan Scheduling of Unit Jobs with Precedence Constraints in O(1.995^n) time
In a classical scheduling problem, we are given a set of n jobs of unit ...
research
∙
01/23/2022
Bounding generalized coloring numbers of planar graphs using coin models
We study Koebe orderings of planar graphs: vertex orderings obtained by ...
research
∙
10/06/2021
Tight bounds for counting colorings and connected edge sets parameterized by cutwidth
We study the fine-grained complexity of counting the number of colorings...
research
∙
06/22/2021
On the Parameterized Complexity of the Connected Flow and Many Visits TSP Problem
We study a variant of Min Cost Flow in which the flow needs to be connec...
research
∙
05/31/2021
Parameterized Problems Complete for Nondeterministic FPT time and Logarithmic Space
Let XNLP be the class of parameterized problems such that an instance of...
research
∙
05/04/2021
Isolation schemes for problems on decomposable graphs
The Isolation Lemma of Mulmuley, Vazirani and Vazirani [Combinatorica'87...
research
∙
11/07/2020
A Gap-ETH-Tight Approximation Scheme for Euclidean TSP
We revisit the classic task of finding the shortest tour of n points in ...
research
∙
10/16/2020
Improving Schroeppel and Shamir's Algorithm for Subset Sum via Orthogonal Vectors
We present an 𝒪^⋆(2^0.5n) time and 𝒪^⋆(2^0.249999n) space randomized alg...
research
∙
07/16/2020
A Faster Exponential Time Algorithm for Bin Packing With a Constant Number of Bins via Additive Combinatorics
In the Bin Packing problem one is given n items with weights w_1,…,w_n a...
research
∙
02/11/2020
Hamiltonian Cycle Parameterized by Treedepth in Single Exponential Time and Polynomial Space
For many algorithmic problems on graphs of treewidth t, a standard dynam...
research
∙
12/06/2019
Parameterized Complexity of Partial Scheduling
We study a natural variant of scheduling that we call partial scheduling...
research
∙
06/28/2019
Detecting Feedback Vertex Sets of Size k in O^(2.7^k) Time
In the Feedback Vertex Set problem, one is given an undirected graph G a...
research
∙
05/07/2019
Equal-Subset-Sum Faster Than the Meet-in-the-Middle
In the Equal-Subset-Sum problem, we are given a set S of n integers and ...
research
∙
04/25/2019
Detecting and Counting Small Patterns in Planar Graphs in Subexponential Parameterized Time
We present an algorithm that takes as input an n-vertex planar graph G a...
research
∙
02/05/2019
Hamiltonicity below Dirac's condition
Dirac's theorem (1952) is a classical result of graph theory, stating th...
research
∙
11/16/2018
Nearly ETH-Tight Algorithms for Planar Steiner Tree with Terminals on Few Faces
The Planar Steiner Tree problem is one of the most fundamental NP-comple...
research
∙
06/27/2018
Computing the Chromatic Number Using Graph Decompositions via Matrix Rank
Computing the smallest number q such that the vertices of a given graph ...
research
∙
05/22/2018
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
The Strong Exponential Time Hypothesis and the OV-conjecture are two pop...
research
∙
09/07/2017
A Tight Lower Bound for Counting Hamiltonian Cycles via Matrix Rank
For even k, the matchings connectivity matrix M_k encodes which pairs of...
research
∙
08/11/2017
New Tools and Connections for Exponential-time Approximation
In this paper, we develop new tools and connections for exponential time...
research
∙
07/05/2017