7 papers · 1 filter
Robust Contraction Decomposition for Minor-Free Graphs and its Applications
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +6
We prove a robust contraction decomposition theorem for -minor-free graphs, which states that given an -minor-free graph and an integer , one can partition in polynomi…
Parameterized Approximation for Capacitated -Hitting Set with Hard Capacities
Daniel Lokshtanov, Abhishek Sahu, Saket Saurabh +2
The \textsc{Capacitated -Hitting Set} problem involves a universe with a capacity function and a collection of subsets…
Efficient Approximation of Fractional Hypertree Width
Viktoriia Korchemna, Daniel Lokshtanov, Saket Saurabh +2
We give two new approximation algorithms to compute the fractional hypertree width of an input hypergraph. The first algorithm takes as input -vertex -edge hypergraph of…
Subexponential Parameterized Algorithms for Hitting Subgraphs
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
For a finite set of graphs, the -Hitting problem aims to compute, for a given graph (taken from some graph class ) of vertices (and…
Bipartizing (Pseudo-)Disk Graphs: Approximation with a Ratio Better than 3
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
In a disk graph, every vertex corresponds to a disk in and two vertices are connected by an edge whenever the two corresponding disks intersect. Disk graphs form an…
An -Time Approximation Scheme for Geometric Many-to-Many Matching
Sayan Bandyapadhyay, Jie Xue
Geometric matching is an important topic in computational geometry and has been extensively studied over decades. In this paper, we study a geometric-matching problem, known as geo…
Enclosing Points with Geometric Objects
Timothy M. Chan, Qizheng He, Jie Xue
Let be a set of points in and be a set of geometric objects in , where . We study the problem of computing a…