
DynamiQ: Planning for Dynamics in Network Streaming Analytics Systems
The emergence of programmable dataplane targets has motivated a new hyb...
read it

Diversity in Kemeny Rank Aggregation: A Parameterized Approach
In its most traditional setting, the main concern of optimization theory...
read it

Elimination Distance to Topologicalminorfree Graphs is FPT
In the literature on parameterized graph problems, there has been an inc...
read it

An Exponential Time Parameterized Algorithm for Planar Disjoint Paths
In the Disjoint Paths problem, the input is an undirected graph G on n v...
read it

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 ...
read it

Efficient Graph Minors Theory and Parameterized Algorithms for (Planar) Disjoint Paths
In the Disjoint Paths problem, the input consists of an nvertex graph G...
read it

Independent Set on C_≥ kFree Graphs in QuasiPolynomial Time
We give an algorithm that takes as input a graph G with weights on the v...
read it

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 ...
read it

Computing the Largest Bond and the Maximum Connected Cut of a Graph
The cutset ∂(S) of a graph G=(V,E) is the set of edges that have one en...
read it

On the Parameterized Approximability of Contraction to Classes of Chordal Graphs
A graph operation that contracts edges is one of the fundamental operati...
read it

Independent Set on P_kFree Graphs in QuasiPolynomial Time
We present an algorithm that takes as input a graph G with weights on th...
read it

A Parameterized Approximation Scheme for Min kCut
In the Min kCut problem, input is an edge weighted graph G and an integ...
read it

Computation of Hadwiger Number and Related Contraction Problems: Tight Lower Bounds
We prove that the Hadwiger number of an nvertex graph G (the maximum si...
read it

The Parameterized Complexity of Guarding Almost Convex Polygons
Art Gallery is a fundamental visibility problem in Computational Geometr...
read it

bColoring Parameterized by CliqueWidth
We provide a polynomialtime algorithm for bColoring on graphs of const...
read it

ETHTight Algorithms for Long Path and Cycle on Unit Disk Graphs
We present an algorithm for the extensively studied Long Path and Long C...
read it

Removing Connected Obstacles in the Plane is FPT
Given two points in the plane, a set of obstacles defined by closed curv...
read it

Faster and Enhanced InclusionMinimal Cograph Completion
We design two incremental algorithms for computing an inclusionminimal ...
read it

Computing the largest bond of a graph
A bond of a graph G is an inclusionwise minimal disconnecting set of G,...
read it

On the Parameterized Complexity of Reconfiguration of Connected Dominating Sets
In a reconfiguration version of an optimization problem Q the input is a...
read it

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) ...
read it

Reducing Topological Minor Containment to the Unique Linkage Theorem
In the Topological Minor Containment problem (TMC) problem two undirecte...
read it

Decomposition of Map Graphs with Applications
Bidimensionality is the most common technique to design subexponentialt...
read it

Slightly Superexponential Parameterized Problems
A central problem in parameterized algorithms is to obtain algorithms ...
read it

Covering Vectors by Spaces in Perturbed Graphic Matroids and Their Duals
Perturbed graphic matroids are binary matroids that can be obtained from...
read it

Going Far From Degeneracy
An undirected graph G is ddegenerate if every subgraph of G has a verte...
read it

Randomized contractions meet lean decompositions
The randomized contractions technique, introduced by Chitnis et al. in 2...
read it

A 2Approximation Algorithm for Feedback Vertex Set in Tournaments
A tournament is a directed graph T such that every pair of vertices is ...
read it

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...
read it

Approximation Schemes for LowRank Binary Matrix Approximation Problems
We provide a randomized linear time approximation scheme for a generic p...
read it

A New Perspective on FO Model Checking of Dense Graph Classes
We study the firstorder (FO) model checking problem of dense graphs, na...
read it

Subexponentialtime Algorithms for Maximum Independent Set in P_tfree and Broomfree Graphs
In algorithmic graph theory, a classic open question is to determine the...
read it

Reducing CMSO Model Checking to Highly Connected Graphs
Given a Counting Monadic Second Order (CMSO) sentence ψ, the CMSO[ψ] pro...
read it

Algorithms for lowdistortion embeddings into arbitrary 1dimensional spaces
We study the problem of finding a minimumdistortion embedding of the sh...
read it

Clustering with Local Restrictions
We study a family of graph clustering problems where each cluster has to...
read it

Covering vectors by spaces: Regular matroids
Seymour's decomposition theorem for regular matroids is a fundamental re...
read it

The complexity of independent set reconfiguration on bipartite graphs
We settle the complexity of the Independent Set Reconfiguration problem ...
read it
Daniel Lokshtanov
is this you? claim profile