research
∙
09/10/2023
How to assign volunteers to tasks compatibly ? A graph theoretic and parameterized approach
In this paper we study a resource allocation problem that encodes correl...
share
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 ...
research
∙
08/14/2023
Kernelization for Spreading Points
We consider the following problem about dispersing points. Given a set o...
research
∙
08/11/2023
Lossy Kernelization for (Implicit) Hitting Set Problems
We re-visit the complexity of kernelization for the d-Hitting Set proble...
research
∙
08/04/2023
Kernelization of Counting Problems
We introduce a new framework for the analysis of preprocessing routines ...
research
∙
08/03/2023
Meta-theorems for Parameterized Streaming Algorithms
The streaming model was introduced to parameterized complexity independe...
research
∙
07/17/2023
Fixed-Parameter Algorithms for Fair Hitting Set Problems
Selection of a group of representatives satisfying certain fairness cons...
research
∙
05/06/2023
Minimum-Membership Geometric Set Cover, Revisited
We revisit a natural variant of geometric set cover, called minimum-memb...
research
∙
04/26/2023
Hitting Subgraphs in Sparse Graphs and Geometric Intersection Graphs
We investigate a fundamental vertex-deletion problem called (Induced) Su...
research
∙
04/06/2023
Parameterized algorithms for Eccentricity Shortest Path Problem
Given an undirected graph G=(V,E) and an integer ℓ, the Eccentricity Sho...
research
∙
03/20/2023
An Improved Exact Algorithm for Knot-Free Vertex Deletion
A knot K in a directed graph D is a strongly connected component of size...
research
∙
03/14/2023
FPT Constant-Approximations for Capacitated Clustering to Minimize the Sum of Cluster Radii
Clustering with capacity constraints is a fundamental problem that attra...
research
∙
12/01/2022
Clustering What Matters: Optimal Approximation for Clustering with Outliers
Clustering with outliers is one of the most fundamental problems in Comp...
research
∙
11/17/2022
(Re)packing Equal Disks into Rectangle
The problem of packing of equal disks (or circles) into a rectangle is a...
research
∙
11/04/2022
A Framework for Approximation Schemes on Disk Graphs
We initiate a systematic study of approximation schemes for fundamental ...
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...
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,...
research
∙
10/08/2022
A Finite Algorithm for the Realizabilty of a Delaunay Triangulation
The Delaunay graph of a point set P ⊆ℝ^2 is the plane graph with the ver...
research
∙
08/14/2022
Exact Exponential Algorithms for Clustering Problems
In this paper we initiate a systematic study of exact algorithms for wel...
research
∙
08/06/2022
Parameterized Algorithms for Locally Minimal Defensive Alliance
A set D of vertices of a graph is a defensive alliance if, for each elem...
research
∙
08/03/2022
Maximum Minimal Feedback Vertex Set: A Parameterized Perspective
In this paper we study a maximization version of the classical Feedback ...
research
∙
03/17/2022
Parameterized and Exact Algorithms for Class Domination Coloring
A class domination coloring (also called cd-Coloring or dominated colori...
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...
research
∙
02/24/2022
Parameterized Complexity of Graph Partitioning into Connected Clusters
Given an undirected graph G and q integers n_1,n_2,n_3, ⋯, n_q, balanced...
research
∙
01/10/2022
Detours in Directed Graphs
We study two "above guarantee" versions of the classical Longest Path pr...
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...
research
∙
07/14/2021
ETH Tight Algorithms for Geometric Intersection Graphs: Now in Polynomial Space
De Berg et al. in [SICOMP 2020] gave an algorithmic framework for subexp...
research
∙
06/27/2021
α-approximate Reductions: a Novel Source of Heuristics for Better Approximation Algorithms
Lokshtanov et al. [STOC 2017] introduced lossy kernelization as a mathem...
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...
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...
research
∙
02/19/2021
Gerrymandering on graphs: Computational complexity and parameterized algorithms
Partitioning a region into districts to favor a particular candidate or ...
research
∙
01/12/2021
Diverse Collections in Matroids and Graphs
We investigate the parameterized complexity of finding diverse sets of s...
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 ...
research
∙
09/26/2020
Improved FPT Algorithms for Deletion to Forest-like Structures
The Feedback Vertex Set problem is undoubtedly one of the most well-stud...
research
∙
09/24/2020
On the Parameterized Complexity of Maximum Degree Contraction Problem
In the Maximum Degree Contraction problem, input is a graph G on n verti...
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...
research
∙
08/18/2020
On the Parameterized Complexity Of Grid Contraction
For a family of graphs 𝒢, the 𝒢-Contraction problem takes as an input a ...
research
∙
08/18/2020
Parameterized Complexity of Maximum Edge Colorable Subgraph
A graph H is p-edge colorable if there is a coloring ψ: E(H) →{1,2,…,p},...
research
∙
08/10/2020
Approximation in (Poly-) Logarithmic Space
We develop new approximation algorithms for classical graph and set prob...
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...
research
∙
05/17/2020
On the (Parameterized) Complexity of Almost Stable Marriage
In the Stable Marriage problem. when the preference lists are complete, ...
research
∙
05/04/2020
On the Parameterized Complexity of Deletion to H-free Strong Components
Directed Feedback Vertex Set (DFVS) is a fundamental computational prob...
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...
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...
research
∙
03/17/2020
The Parameterized Complexity of Guarding Almost Convex Polygons
Art Gallery is a fundamental visibility problem in Computational Geometr...
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...
research
∙
01/24/2020
Fixed-parameter tractable algorithms for Tracking Shortest Paths
We consider the parameterized complexity of the problem of tracking shor...
research
∙
11/09/2019
A Polynomial Kernel for Paw-Free Editing
For a fixed graph H, the H-free-editing problem asks whether we can modi...
research
∙
06/13/2019
Structural Parameterization for Graph Deletion Problems over Data Streams
The study of parameterized streaming complexity on graph problems was in...
research
∙
06/13/2019