121 citations · 373 across the 96 of their papers we have counts for
15 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…
Faster Exact and Parameterized Algorithm for Feedback Vertex Set in Bipartite Tournaments
Mithilesh Kumar, Daniel Lokshtanov
A {\em bipartite tournament} is a directed graph such that every pair of vertices are connected by an arc, and no arc connects two vertice…
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…
Parameterized Saga of First-Fit and Last-Fit Coloring
Akanksha Agrawal, Daniel Lokshtanov, Fahad Panolan +2
The classic greedy coloring (first-fit) algorithm considers the vertices of an input graph in a given order and assigns the first available color to each vertex in . In…
Fixed-Parameter Tractability of Hedge Cut
Fedor V. Fomin, Petr A. Golovach, Tuukka Korhonen +2
In the Hedge Cut problem, the edges of a graph are partitioned into groups called hedges, and the question is what is the minimum number of hedges to delete to disconnect the graph…
Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
Daniel Lokshtanov, Paweł Rzążewski, Saket Saurabh +2
In this article we show that Maximum Partial List H-Coloring is polynomial-time solvable on P_5-free graphs for every fixed graph H. In particular, this implies that Maximum k-Colo…
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…
Tree Independence Number IV. Even-hole-free Graphs
Maria Chudnovsky, Peter Gartland, Sepehr Hajebi +2
We prove that the tree independence number of every even-hole-free graph is at most polylogarithmic in its number of vertices. More explicitly, we prove that there exists a constan…
When far is better: The Chamberlin-Courant approach to obnoxious committee selection
Sushmita Gupta, Tanmay Inamdar, Pallavi Jain +3
Classical work on metric space based committee selection problem interprets distance as ``near is better''. In this work, motivated by real-life situations, we interpret distance a…
Tree independence number II. Three-path-configurations
Maria Chudnovsky, Sepehr Hajebi, Daniel Lokshtanov +1
A three-path-configuration is a graph consisting of three pairwise internally-disjoint paths the union of every two of which is an induced cycle of length at least four. A graph is…
Satisfiability to Coverage in Presence of Fairness, Matroid, and Global Constraints
Tanmay Inamdar, Pallavi Jain, Daniel Lokshtanov +3
In MaxSAT with Cardinality Constraint problem (CC-MaxSAT), we are given a CNF-formula , and , and the goal is to find an assignment with at most variables set t…
Odd Cycle Transversal on -free Graphs in Polynomial Time
Akanksha Agrawal, Paloma T. Lima, Daniel Lokshtanov +3
An independent set in a graph G is a set of pairwise non-adjacent vertices. A graph is bipartite if its vertex set can be partitioned into two independent sets. In the Odd Cycl…
Induced subgraphs and tree decompositions XV. Even-hole-free graphs with bounded clique number have logarithmic treewidth
Maria Chudnovsky, Peter Gartland, Sepehr Hajebi +2
We prove that for every integer there exists an integer such that every -vertex even-hole-free graph with no clique of size has treewidth at most $c_t\…