Daniel Lokshtanov

research

∙ 09/15/2023

On Induced Versions of Menger's Theorem on Sparse Graphs

Let A and B be sets of vertices in a graph G. Menger's theorem states th...

0 Peter Gartland, et al. ∙

research

∙ 08/29/2023

Lower Bound for Independence Covering in C_4-Free Graphs

An independent set in a graph G is a set S of pairwise non-adjacent vert...

0 Michael Kuhn, et al. ∙

research

∙ 08/21/2023

Parameterized Complexity of Fair Bisection: FPT-Approximation meets Unbreakability

In the Minimum Bisection problem, input is a graph G and the goal is to ...

0 Tanmay Inamdar, et al. ∙

research

∙ 08/18/2023

Counting and Sampling Labeled Chordal Graphs in Polynomial Time

We present the first polynomial-time algorithm to exactly compute the nu...

0 Úrsula Hébert-Johnson, et al. ∙

research

∙ 08/11/2023

Lossy Kernelization for (Implicit) Hitting Set Problems

We re-visit the complexity of kernelization for the d-Hitting Set proble...

0 Fedor V. Fomin, et al. ∙

research

∙ 08/09/2023

Induced-Minor-Free Graphs: Separator Theorem, Subexponential Algorithms, and Improved Hardness of Recognition

A graph G contains a graph H as an induced minor if H can be obtained fr...

0 Tuukka Korhonen, et al. ∙

research

∙ 08/04/2023

Kernelization of Counting Problems

We introduce a new framework for the analysis of preprocessing routines ...

0 Daniel Lokshtanov, et al. ∙

research

∙ 08/03/2023

Meta-theorems for Parameterized Streaming Algorithms

The streaming model was introduced to parameterized complexity independe...

0 Daniel Lokshtanov, et al. ∙

research

∙ 05/25/2023

Maximum Weight Independent Set in Graphs with no Long Claws in Quasi-Polynomial Time

We show that the Maximum Weight Independent Set problem (MWIS) can be so...

0 Peter Gartland, et al. ∙

research

∙ 04/26/2023

Hitting Subgraphs in Sparse Graphs and Geometric Intersection Graphs

We investigate a fundamental vertex-deletion problem called (Induced) Su...

0 Daniel Lokshtanov, et al. ∙

research

∙ 11/14/2022

An Improved Parameterized Algorithm for Treewidth

We give an algorithm that takes as input an n-vertex graph G and an inte...

0 Tuukka Korhonen, et al. ∙

research

∙ 11/09/2022

Shortest Cycles With Monotone Submodular Costs

We introduce the following submodular generalization of the Shortest Cyc...

0 Fedor V. Fomin, et al. ∙

research

∙ 11/04/2022

A Framework for Approximation Schemes on Disk Graphs

We initiate a systematic study of approximation schemes for fundamental ...

0 Daniel Lokshtanov, et al. ∙

research

∙ 10/26/2022

Fixed-parameter tractability of Graph Isomorphism in graphs with an excluded minor

We prove that Graph Isomorphism and Canonization in graphs excluding a f...

0 Daniel Lokshtanov, et al. ∙

research

∙ 10/26/2022

Highly unbreakable graph with a fixed excluded minor are almost rigid

A set X ⊆ V(G) in a graph G is (q,k)-unbreakable if every separation (A,...

0 Daniel Lokshtanov, et al. ∙

research

∙ 03/30/2022

Wordle is NP-hard

Wordle is a single-player word-guessing game where the goal is to discov...

0 Daniel Lokshtanov, et al. ∙

research

∙ 03/15/2022

Point Separation and Obstacle Removal by Finding and Hitting Odd Cycles

Suppose we are given a pair of points s, t and a set S of n geometric ob...

0 Neeraj Kumar, et al. ∙

research

∙ 11/28/2021

Subexponential Parameterized Algorithms for Cut and Cycle Hitting Problems on H-Minor-Free Graphs

We design the first subexponential-time (parameterized) algorithms for s...

0 Sayan Bandyapadhyay, et al. ∙

research

∙ 06/09/2021

DynamiQ: Planning for Dynamics in Network Streaming Analytics Systems

The emergence of programmable data-plane targets has motivated a new hyb...

0 Rohan Bhatia, et al. ∙

research

∙ 05/19/2021

Diversity in Kemeny Rank Aggregation: A Parameterized Approach

In its most traditional setting, the main concern of optimization theory...

0 Emmanuel Arrighi, et al. ∙

research

∙ 04/20/2021

Elimination Distance to Topological-minor-free Graphs is FPT

In the literature on parameterized graph problems, there has been an inc...

0 Akanksha Agrawal, et al. ∙

research

∙ 03/31/2021

An Exponential Time Parameterized Algorithm for Planar Disjoint Paths

In the Disjoint Paths problem, the input is an undirected graph G on n v...

0 Daniel Lokshtanov, et al. ∙

research

∙ 11/29/2020

A Constant Factor Approximation for Navigating Through Connected Obstacles in the Plane

Given two points s and t in the plane and a set of obstacles defined by ...

0 Neeraj Kumar, et al. ∙

research

∙ 08/19/2020

Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths

In the Disjoint Paths problem, the input consists of an n-vertex graph G...

0 Daniel Lokshtanov, et al. ∙

research

∙ 07/21/2020

Independent Set on C_≥ k-Free Graphs in Quasi-Polynomial Time

We give an algorithm that takes as input a graph G with weights on the v...

0 Peter Gartland, et al. ∙

research

∙ 07/17/2020

Dominated Minimal Separators are Tame (Nearly All Others are Feral)

A class F of graphs is called tame if there exists a constant k so that ...

0 Peter Gartland, et al. ∙

research

∙ 07/09/2020

Computing the Largest Bond and the Maximum Connected Cut of a Graph

The cut-set ∂(S) of a graph G=(V,E) is the set of edges that have one en...

0 Gabriel L. Duarte, et al. ∙

research

∙ 06/18/2020

On the Parameterized Approximability of Contraction to Classes of Chordal Graphs

A graph operation that contracts edges is one of the fundamental operati...

0 Spoorthy Gunda, et al. ∙

research

∙ 05/02/2020

Independent Set on P_k-Free Graphs in Quasi-Polynomial Time

We present an algorithm that takes as input a graph G with weights on th...

0 Peter Gartland, et al. ∙

research

∙ 04/30/2020

A Parameterized Approximation Scheme for Min k-Cut

In the Min k-Cut problem, input is an edge weighted graph G and an integ...

0 Daniel Lokshtanov, et al. ∙

research

∙ 04/24/2020

Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds

We prove that the Hadwiger number of an n-vertex graph G (the maximum si...

0 Fedor V. Fomin, et al. ∙

research

∙ 03/17/2020

The Parameterized Complexity of Guarding Almost Convex Polygons

Art Gallery is a fundamental visibility problem in Computational Geometr...

0 Akanksha Agrawal, et al. ∙

research

∙ 03/09/2020

b-Coloring Parameterized by Clique-Width

We provide a polynomial-time algorithm for b-Coloring on graphs of const...

0 Lars Jaffke, et al. ∙

research

∙ 03/02/2020

ETH-Tight Algorithms for Long Path and Cycle on Unit Disk Graphs

We present an algorithm for the extensively studied Long Path and Long C...

0 Fedor V. Fomin, et al. ∙

research

∙ 02/04/2020

Removing Connected Obstacles in the Plane is FPT

Given two points in the plane, a set of obstacles defined by closed curv...

0 Eduard Eiben, et al. ∙

research

∙ 01/21/2020

Faster and Enhanced Inclusion-Minimal Cograph Completion

We design two incremental algorithms for computing an inclusion-minimal ...

0 Christophe Crespelle, et al. ∙

research

∙ 10/02/2019

Computing the largest bond of a graph

A bond of a graph G is an inclusion-wise minimal disconnecting set of G,...

0 Gabriel L. Duarte, et al. ∙

research

∙ 10/01/2019

On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets

In a reconfiguration version of an optimization problem Q the input is a...

0 Daniel Lokshtanov, et al. ∙

research

∙ 04/17/2019

A Brief Note on Single Source Fault Tolerant Reachability

Let G be a directed graph with n vertices and m edges, and let s ∈ V(G) ...

0 Daniel Lokshtanov, et al. ∙

research

∙ 04/05/2019

Reducing Topological Minor Containment to the Unique Linkage Theorem

In the Topological Minor Containment problem (TMC) problem two undirecte...

0 Fedor V. Fomin, et al. ∙

research

∙ 03/04/2019

Decomposition of Map Graphs with Applications

Bidimensionality is the most common technique to design subexponential-t...

0 Fedor V. Fomin, et al. ∙

research

∙ 02/23/2019

Slightly Superexponential Parameterized Problems

A central problem in parameterized algorithms is to obtain algorithms ...

0 Daniel Lokshtanov, et al. ∙

research

∙ 02/19/2019

Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals

Perturbed graphic matroids are binary matroids that can be obtained from...

0 Fedor V. Fomin, et al. ∙

research

∙ 02/07/2019

Going Far From Degeneracy

An undirected graph G is d-degenerate if every subgraph of G has a verte...

0 Fedor V. Fomin, et al. ∙

research

∙ 10/16/2018

Randomized contractions meet lean decompositions

The randomized contractions technique, introduced by Chitnis et al. in 2...

0 Marek Cygan, et al. ∙

research

∙ 09/22/2018

A 2-Approximation Algorithm for Feedback Vertex Set in Tournaments

A tournament is a directed graph T such that every pair of vertices is ...

0 Daniel Lokshtanov, et al. ∙

research

∙ 08/07/2018

The Parameterized Complexity of Finding Point Sets with Hereditary Properties

We consider problems where the input is a set of points in the plane and...

0 David Eppstein, et al. ∙

research

∙ 07/18/2018

Approximation Schemes for Low-Rank Binary Matrix Approximation Problems

We provide a randomized linear time approximation scheme for a generic p...

0 Fedor V. Fomin, et al. ∙

research

∙ 05/04/2018

A New Perspective on FO Model Checking of Dense Graph Classes

We study the first-order (FO) model checking problem of dense graphs, na...

0 Jakub Gajarsky, et al. ∙

research

∙ 04/11/2018

Subexponential-time Algorithms for Maximum Independent Set in P_t-free and Broom-free Graphs

In algorithmic graph theory, a classic open question is to determine the...

0 Gábor Bacsó, et al. ∙

Daniel Lokshtanov

Featured Co-authors