1 citations · 2 across the 6 of their papers we have counts for
7 papers · 1 filter
A Dividing Line for Structural Kernelization of Component Order Connectivity via Distance to Bounded Pathwidth
Jakob Greilhuber, Roohani Sharma
In this work we study a classic generalization of the Vertex Cover (VC) problem, called the Component Order Connectivity (COC) problem. In COC, given an undirected graph , integ…
Protrusion Decompositions Revisited: Uniform Lossy Kernels for Reducing Treewidth and Linear Kernels for Hitting Disconnected Minors
Roohani Sharma, Michał Włodarczyk
Let F be a finite family of graphs. In the F-Deletion problem, one is given a graph G and an integer k, and the goal is to find k vertices whose deletion results in a graph with no…
Maximum Partial List H-Coloring on P_5-free graphs in polynomial time
Daniel Lokshtanov, Paweł Rzążewski, Saket Saurabh +2
In this article we show that Maximum Partial List H-Coloring is polynomial-time solvable on P_5-free graphs for every fixed graph H. In particular, this implies that Maximum k-Colo…
Parameterized Complexity of Weighted Multicut in Trees
Esther Galby, Dániel Marx, Philipp Schepper +2
The Edge Multicut problem is a classical cut problem where given an undirected graph , a set of pairs of vertices , and a budget , the goal is to determine if th…
On the Parameterized Complexity of Deletion to -free Strong Components
Rian Neogi, M. S. Ramanujan, Saket Saurabh +1
{\sc Directed Feedback Vertex Set (DFVS)} is a fundamental computational problem that has received extensive attention in parameterized complexity. In this paper, we initiate the s…
Balanced Judicious Partition is Fixed-Parameter Tractable
Daniel Lokshtanov, Saket Saurabh, Roohani Sharma +1
The family of judicious partitioning problems, introduced by Bollobás and Scott to the field of extremal combinatorics, has been extensively studied from a structural point of view…