3 papers
cs.DS2026
Hardness of Vertex Splitting: Cographs, Chordal Graphs, and Beyond
Satyabrata Jana, Shivesh K. Roy, R. B. Sandeep
Vertex splitting replaces a vertex (v) by two nonadjacent vertices whose neighborhoods together equal (N(v)). A split is \emph{exclusive} if these neighborhoods are disjoint and \e…
cs.DS2023
On the Parameterized Complexity of Multiway Near-Separator
Bart M. P. Jansen, Shivesh K. Roy
We study a new graph separation problem called Multiway Near-Separator. Given an undirected graph , integer , and terminal set , it asks whether there is a…
cs.DS2021
On the Hardness of Compressing Weights
Bart M. P. Jansen, Shivesh K. Roy, Michał Włodarczyk
We investigate computational problems involving large weights through the lens of kernelization, which is a framework of polynomial-time preprocessing aimed at compressing the inst…