research
∙
08/03/2023
Meta-theorems for Parameterized Streaming Algorithms
The streaming model was introduced to parameterized complexity independe...
share
research
∙
08/02/2023
Polynomial-delay Enumeration Kernelizations for Cuts of Bounded Degree
Enumeration kernelization was first proposed by Creignou et al. [TOCS 20...
research
∙
12/01/2022
An Improved Time-Efficient Approximate Kernelization for Connected Treedepth Deletion Set
We study the CONNECTED η-TREEDEPTH DELETION problem where the input inst...
research
∙
05/04/2022
On the Complexity of Majority Illusion in Social Networks
Majority illusion occurs in a social network when the majority of the ne...
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
∙
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
∙
06/18/2019
On the Constrained Least-cost Tour Problem
We introduce the Constrained Least-cost Tour (CLT) problem: given an und...
research
∙
05/08/2019
On the Approximate Compressibility of Connected Vertex Cover
The Connected Vertex Cover problem, where the goal is to compute a minim...
research
∙
12/05/2018
On the Complexity Landscape of Connected f -Factor Problems
Let G be an undirected simple graph having n vertices and let f be a fun...
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...
research
∙
04/27/2018
Alternative parameterizations of Metric Dimension
A set of vertices W in a graph G is called resolving if for any two dist...
research
∙
02/05/2018
Reducing CMSO Model Checking to Highly Connected Graphs
Given a Counting Monadic Second Order (CMSO) sentence ψ, the CMSO[ψ] pro...
research
∙
11/06/2017