research
∙
07/20/2023
Parameterized Complexity of Biclique Contraction and Balanced Biclique Contraction
In this work, we initiate the complexity study of Biclique Contraction a...
share
research
∙
07/16/2023
Tight (Double) Exponential Bounds for NP-Complete Problems: Treewidth and Vertex Cover Parameterizations
Treewidth is as an important parameter that yields tractability for many...
research
∙
10/05/2022
Romeo and Juliet Meeting in Forest Like Regions
The game of rendezvous with adversaries is a game on a graph played by t...
research
∙
08/04/2022
Domination and Cut Problems on Chordal Graphs with Bounded Leafage
The leafage of a chordal graph G is the minimum integer l such that G ca...
research
∙
06/30/2022
Metric Dimension Parameterized by Feedback Vertex Set and Other Structural Parameters
For a graph G, a subset S ⊆ V(G) is called a resolving set if for any tw...
research
∙
06/15/2022
The Complexity of Contracting Bipartite Graphs into Small Cycles
For a positive integer ℓ≥ 3, the C_ℓ-Contractibility problem takes as in...
research
∙
05/20/2022
Parameterized Complexity of Weighted Multicut in Trees
The Edge Multicut problem is a classical cut problem where given an undi...
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/16/2022
Sparsification Lower Bound for Linear Spanners in Directed Graphs
For α≥ 1, β≥ 0, and a graph G, a spanning subgraph H of G is said to be ...
research
∙
02/07/2022
Reducing the Vertex Cover Number via Edge Contractions
The CONTRACTION(vc) problem takes as input a graph G on n vertices and t...
research
∙
10/28/2021
A Framework for Parameterized Subexponential Algorithms for Generalized Cycle Hitting Problems on Planar Graphs
Subexponential parameterized algorithms are known for a wide range of na...
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
∙
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/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
∙
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
∙
01/08/2019