3 papers
cs.CG2025
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…
cs.CC2024
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…
cs.DS2023
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…