research
∙
09/18/2023
How to Make Knockout Tournaments More Popular?
Given a mapping from a set of players to the leaves of a complete binary...
share
research
∙
08/14/2023
Kernelization for Spreading Points
We consider the following problem about dispersing points. Given a set o...
research
∙
08/11/2023
Finding Long Directed Cycles Is Hard Even When DFVS Is Small Or Girth Is Large
We study the parameterized complexity of two classic problems on directe...
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/18/2023
𝒫-matchings Parameterized by Treewidth
A matching is a subset of edges in a graph G that do not share an endpoi...
research
∙
07/13/2023
Planar Disjoint Paths, Treewidth, and Kernels
In the Planar Disjoint Paths problem, one is given an undirected planar ...
research
∙
07/11/2023
Parameterized Results on Acyclic Matchings with Implications for Related Problems
A matching M in a graph G is an acyclic matching if the subgraph of G in...
research
∙
07/10/2023
Parameterized Analysis of the Cops and Robber Problem
Pursuit-evasion games have been intensively studied for several decades ...
research
∙
04/26/2023
Hitting Subgraphs in Sparse Graphs and Geometric Intersection Graphs
We investigate a fundamental vertex-deletion problem called (Induced) Su...
research
∙
01/25/2023
In Which Graph Structures Can We Efficiently Find Temporally Disjoint Paths and Walks?
A temporal graph has an edge set that may change over discrete time step...
research
∙
01/15/2023
Long Directed Detours: Reduction to 2-Disjoint Paths
We study an "above guarantee" version of the Longest Path problem in dir...
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/10/2022
Parameterized Approaches to Orthogonal Compaction
Orthogonal graph drawings are used in applications such as UML diagrams,...
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/23/2021
The complexity of high-dimensional cuts
Cut problems form one of the most fundamental classes of problems in alg...
research
∙
06/30/2021
Grid Recognition: Classical and Parameterized Computational Perspectives
Grid graphs, and, more generally, k× r grid graphs, form one of the most...
research
∙
05/21/2021
Verification of Multi-Layered Assignment Problems
The class of assignment problems is a fundamental and well-studied class...
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/07/2021
Multivariate Analysis of Scheduling Fair Competitions
A fair competition, based on the concept of envy-freeness, is a non-elim...
research
∙
12/09/2020
Participatory Budgeting with Project Groups
We study a generalization of the standard approval-based model of partic...
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
∙
05/17/2020
On the (Parameterized) Complexity of Almost Stable Marriage
In the Stable Marriage problem. when the preference lists are complete, ...
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
∙
04/20/2020
Parameterized Study of Steiner Tree on Unit Disk Graphs
We study the Steiner Tree problem on unit disk graphs. Given a n vertex ...
research
∙
04/01/2020
Parameterized Analysis of Assignment Under Multiple Preferences
The Assignment problem is a fundamental, well-studied problem in the int...
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
∙
12/04/2019
A New Paradigm for Identifying Reconciliation-Scenario Altering Mutations Conferring Environmental Adaptation
An important goal in microbial computational genomics is to identify cru...
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) ...
research
∙
04/05/2019
Reducing Topological Minor Containment to the Unique Linkage Theorem
In the Topological Minor Containment problem (TMC) problem two undirecte...
research
∙
03/06/2019
The Parameterized Complexity of Motion Planning for Snake-Like Robots
We study the parameterized complexity of a variant of the classic video ...
research
∙
03/04/2019
Decomposition of Map Graphs with Applications
Bidimensionality is the most common technique to design subexponential-t...
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...
research
∙
02/07/2019
Going Far From Degeneracy
An undirected graph G is d-degenerate if every subgraph of G has a verte...
research
∙
06/24/2018
On r-Simple k-Path and Related Problems Parameterized by k/r
Abasi et al. (2014) and Gabizon et al. (2015) studied the following prob...
research
∙
03/25/2018
Popular Matching in Roommates Setting is NP-hard
An input to the Popular Matching problem, in the roommates setting, cons...
research
∙
02/20/2018
The Parameterized Complexity of Packing Arc-Disjoint Cycles in Tournaments
Given a directed graph D on n vertices and a positive integer k, the Arc...
research
∙
02/05/2018
Reducing CMSO Model Checking to Highly Connected Graphs
Given a Counting Monadic Second Order (CMSO) sentence ψ, the CMSO[ψ] pro...
research
∙
07/17/2017