15 papers
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…
Witness Set: A Visibility Problem in
Satyabrata Jana, Debabrata Pal, Bodhayan Roy +1
We study the Witness Set problem, a natural dual to the classical Art Gallery problem. In the Witness Set problem, we are given a polygon and an integer as input, and the o…
FPT Approximations for Connected Maximum Coverage
Tanmay Inamdar, Satyabrata Jana, Madhumita Kundu +3
We revisit connectivity-constrained coverage through a unifying model, Partial Connected Red-Blue Dominating Set. Given a red-blue bipartite graph and an auxiliary connectivity…
Exotic coupled spin-charge states in decorated honeycomb magnets: A hybrid-Monte Carlo study
Satyabrata Jana, Sahinur Reja
We uncover four exotic coupled spin-charge ground states in the strong coupling limit of the Kondo lattice model at various electronic fillings on a frustrated decorated honeycomb…
Witness Set in Monotone Polygons: Exact and Approximate
Udvas Das, Binayak Dutta, Satyabrata Jana +2
Given a simple polygon , two points and within are {\em visible} to each other if the line segment between and is contained in $\mathscr{…
Towards Transitive-free Digraphs
Ankit Abhinav, Satyabrata Jana, Abhishek Sahu
In a digraph , an arc in is considered transitive if there is a path from to in . A digraph is transitive-free if it does not contain any transitive…