7 papers
Fine-Grained Bounds for Courcelle's Theorem
Daniel Lokshtanov, Fahad Panolan, Saket Saurabh +2
Courcelle's theorem states that there exists an algorithm that takes as input a graph of treewidth at most and a MSO formula , and determines whether satisfies …
Parameterized Approximation of Rectangle Stabbing
Huairui Chu, Ajaykrishnan E S, Daniel Lokshtanov +4
In the Rectangle Stabbing problem, input is a set of axis-parallel rectangles and a set of axis parallel lines in the plane. The task is to find a minimum siz…
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…
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…