research
∙
05/12/2023
Minimum Consistent Subset for Trees Revisited
In a vertex-colored graph G = (V, E), a subset S ⊆ V is said to be consi...
share
research
∙
02/14/2023
Grouped Domination Parameterized by Vertex Cover, Twin Cover, and Beyond
A dominating set S of graph G is called an r-grouped dominating set if S...
research
∙
10/06/2022
Sequentially Swapping Tokens: Further on Graph Classes
We study the following variant of the 15 puzzle. Given a graph and two t...
research
∙
07/03/2022
Algorithmic Meta-Theorems for Combinatorial Reconfiguration Revisited
Given a graph and two vertex sets satisfying a certain feasibility condi...
research
∙
03/25/2022
Independent set reconfiguration on directed graphs
Directed Token Sliding asks, given a directed graph and two sets of pair...
research
∙
02/20/2022
Finding shortest non-separating and non-disconnecting paths
For a connected graph G = (V, E) and s, t ∈ V, a non-separating s-t path...
research
∙
02/19/2022
Sorting Balls and Water: Equivalence and Computational Complexity
Various forms of sorting problems have been studied over the years. Rece...
research
∙
02/17/2022
Extended MSO Model Checking via Small Vertex Integrity
We study the model checking problem of an extended 𝖬𝖲𝖮 with local and gl...
research
∙
01/22/2022
A Framework to Design Approximation Algorithms for Finding Diverse Solutions in Combinatorial Problems
Finding a single best solution is the most common objective in combinato...
research
∙
12/10/2021
Computing Diverse Shortest Paths Efficiently: A Theoretical and Experimental Study
Finding diverse solutions in combinatorial problems recently has receive...
research
∙
11/26/2021
Reconfiguration of Regular Induced Subgraphs
We study the problem of checking the existence of a step-by-step transfo...
research
∙
09/06/2021
Computational Complexity of Jumping Block Puzzles
In combinatorial reconfiguration, the reconfiguration problems on a vert...
research
∙
07/07/2021
Reconfiguring Directed Trees in a Digraph
In this paper, we investigate the computational complexity of subgraph r...
research
∙
01/23/2021
Exploring the Gap Between Treedepth and Vertex Cover Through Vertex Integrity
For intractable problems on graphs of bounded treewidth, two graph param...
research
∙
12/09/2020
An Improved Deterministic Parameterized Algorithm for Cactus Vertex Deletion
A cactus is a connected graph that does not contain K_4 - e as a minor. ...
research
∙
09/18/2020
Longest Common Subsequence in Sublinear Space
We present the first o(n)-space polynomial-time algorithm for computing ...
research
∙
09/08/2020
Finding Diverse Trees, Paths, and More
Mathematical modeling is a standard approach to solve many real-world pr...
research
∙
08/17/2020
Grundy Distinguishes Treewidth from Pathwidth
Structural graph parameters, such as treewidth, pathwidth, and clique-wi...
research
∙
08/08/2020
Parameterized Complexity of (A,ℓ)-Path Packing
Given a graph G = (V,E), A ⊆ V, and integers k and ℓ, the (A,ℓ)-Path Pac...
research
∙
07/17/2020
Parameterized Complexity of Graph Burning
Graph Burning asks, given a graph G = (V,E) and an integer k, whether th...
research
∙
02/25/2020
Hedonic Seat Arrangement Problems
In this paper, we study a variant of hedonic games, called Seat Arrangem...
research
∙
09/20/2019
Linear-Time Recognition of Double-Threshold Graphs
A graph G = (V,E) is a double-threshold graph if there exist a vertex-we...
research
∙
08/26/2019
Low-Congestion Shortcut and Graph Parameters
The concept of low-congestion shortcuts is initiated by Ghaffari and Hae...
research
∙
05/25/2019
Subgraph Isomorphism on Graph Classes that Exclude a Substructure
We study Subgraph Isomorphism on graph classes defined by a fixed forbid...
research
∙
05/01/2019
Independent Set Reconfiguration Parameterized by Modular-Width
Independent Set Reconfiguration is one of the most well-studied problems...
research
∙
01/27/2019
Parameterized Complexity of Safe Set
In this paper we study the problem of finding a small safe set S in a gr...
research
∙
07/30/2018
Parameterized Orientable Deletion
A graph is d-orientable if its edges can be oriented so that the maximum...
research
∙
07/14/2018
Token Sliding on Split Graphs
We show that the independent set reconfiguration problem on split graphs...
research
∙
04/23/2018
How Bad is the Freedom to Flood-It?
Fixed-Flood-It and Free-Flood-It are combinatorial problems on graphs th...
research
∙
03/19/2018
Swapping Colored Tokens on Graphs
We investigate the computational complexity of the following problem. We...
research
∙
02/19/2018
Reconfiguration of Colorable Sets in Classes of Perfect Graphs
A set of vertices in a graph is c-colorable if the subgraph induced by t...
research
∙
12/26/2017