8 papers
How to Fix a Broken Metric: A Linear Kernel, Tight Bounds, and Tree Metrics
Sayan Bandyapadhyay, William Lochet, Daniel Lokshtanov +4
Given a complete graph whose edge weights represent dissimilarities, Metric Violation Distance asks whether at most weights can be changed to form a metric. Motivated by metric…
A Quasi-Polynomial Time Algorithm for 3-Coloring Circle Graphs
Ajaykrishnan E S, Robert Ganian, Daniel Lokshtanov +1
A graph is a circle graph if it is an intersection graph of chords of a unit circle. We give an algorithm that takes as input an vertex circle graph , runs in time at mo…
Clustering with Set Outliers and Applications in Relational Clustering
Vaishali Surianarayanan, Neeraj Kumar, Stavros Sintos
We introduce and study the -center clustering problem with set outliers, a natural and practical generalization of the classical -center clustering with outliers. Instead of…
Linear Layouts Revisited: Stacks, Queues, and Exact Algorithms
Thomas Depian, Simon D. Fink, Robert Ganian +1
In spite of the extensive study of stack and queue layouts, many fundamental questions remain open concerning the complexity-theoretic frontiers for computing stack and queue layou…
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…
Parameterized Complexity of Fair Bisection: FPT-Approximation meets Unbreakability
Tanmay Inamdar, Daniel Lokshtanov, Saket Saurabh +1
In the Minimum Bisection problem, input is a graph and the goal is to partition the vertex set into two parts and , such that and the number of edg…
A Parameterized Approximation Scheme for Min -Cut
Daniel Lokshtanov, Saket Saurabh, Vaishali Surianarayanan
In the Min -Cut problem, input is an edge weighted graph and an integer , and the task is to partition the vertex set into non-empty sets, such that the total weight…