
ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space
De Berg et al. in [SICOMP 2020] gave an algorithmic framework for subexp...
read it

αapproximate Reductions: a Novel Source of Heuristics for Better Approximation Algorithms
Lokshtanov et al. [STOC 2017] introduced lossy kernelization as a mathem...
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

Gerrymandering on graphs: Computational complexity and parameterized algorithms
Partitioning a region into districts to favor a particular candidate or ...
read it

Diverse Collections in Matroids and Graphs
We investigate the parameterized complexity of finding diverse sets of s...
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

Improved FPT Algorithms for Deletion to Forestlike Structures
The Feedback Vertex Set problem is undoubtedly one of the most wellstud...
read it

On the Parameterized Complexity of Maximum Degree Contraction Problem
In the Maximum Degree Contraction problem, input is a graph G on n verti...
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

On the Parameterized Complexity Of Grid Contraction
For a family of graphs 𝒢, the 𝒢Contraction problem takes as an input a ...
read it

Parameterized Complexity of Maximum Edge Colorable Subgraph
A graph H is pedge colorable if there is a coloring ψ: E(H) →{1,2,…,p},...
read it

Approximation in (Poly) Logarithmic Space
We develop new approximation algorithms for classical graph and set prob...
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

On the (Parameterized) Complexity of Almost Stable Marriage
In the Stable Marriage problem. when the preference lists are complete, ...
read it

On the Parameterized Complexity of Deletion to Hfree Strong Components
Directed Feedback Vertex Set (DFVS) is a fundamental computational prob...
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

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

Fixedparameter tractable algorithms for Tracking Shortest Paths
We consider the parameterized complexity of the problem of tracking shor...
read it

A Polynomial Kernel for PawFree Editing
For a fixed graph H, the Hfreeediting problem asks whether we can modi...
read it

Structural Parameterization for Graph Deletion Problems over Data Streams
The study of parameterized streaming complexity on graph problems was in...
read it

FixedParameter Tractability of Graph Deletion Problems over Data Streams
In this work, we initiate a systematic study of parameterized streaming ...
read it

On the Approximate Compressibility of Connected Vertex Cover
The Connected Vertex Cover problem, where the goal is to compute a minim...
read it

FPT Algorithms for Conflictfree Coloring of Graphs and Chromatic Terrain Guarding
We present fixed parameter tractable algorithms for the conflictfree co...
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

Subset Feedback Vertex Set in Chordal and Split Graphs
In the Subset Feedback Vertex Set (SubsetFVS) problem the input is a gr...
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

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

Parameterized Query Complexity of Hitting Set using Stability of Sunflowers
In this paper, we study the query complexity of parameterized decision a...
read it

Popular Matching in Roommates Setting is NPhard
An input to the Popular Matching problem, in the roommates setting, cons...
read it

The Parameterized Complexity of Packing ArcDisjoint Cycles in Tournaments
Given a directed graph D on n vertices and a positive integer k, the Arc...
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

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

On Treewidth and Stable Marriage
Stable Marriage is a fundamental problem to both computer science and ec...
read it
Saket Saurabh
is this you? claim profile