5 papers
On Subexponential Parameterized Algorithms for Steiner Tree on Intersection Graphs of Geometric Objects
Sujoy Bhore, Baris Can Esmer, Daniel Marx +1
We study the Steiner Tree problem on the intersection graph of most natural families of geometric objects, e.g., disks, squares, polygons, etc. Given a set of objects in the pl…
Fundamental Problems on Bounded-Treewidth Graphs: The Real Source of Hardness
Barış Can Esmer, Jacob Focke, Dániel Marx +1
It is known for many algorithmic problems that if a tree decomposition of width is given in the input, then the problem can be solved with exponential dependence on . A line…
Approximate Monotone Local Search for Weighted Problems
Baris Can Esmer, Ariel Kulik, Daniel Marx +2
In a recent work, Esmer et al. describe a simple method - Approximate Monotone Local Search - to obtain exponential approximation algorithms from existing parameterized exact algor…
List homomorphisms by deleting edges and vertices: tight complexity bounds for bounded-treewidth graphs
Barış Can Esmer, Jacob Focke, Dániel Marx +1
The goal of this paper is to investigate a family of optimization problems arising from list homomorphisms, and to understand what the best possible algorithms are if we restrict t…
Computing Generalized Convolutions Faster Than Brute Force
Barış Can Esmer, Ariel Kulik, Dániel Marx +2
In this paper, we consider a general notion of convolution. Let be a finite domain and let be the set of -length vectors (tuples) of . Let be…