From the 1 of 10 linked papers with an AI index.
10 papers
Hardness of Vertex Splitting: Cographs, Chordal Graphs, and Beyond
Satyabrata Jana, Shivesh K. Roy, R. B. Sandeep
The paper investigates the computational complexity of transforming graphs into cographs, chordal graphs, unit‑interval graphs, and Pₜ‑free graphs via vertex splitting, proving the…
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{…
On the Parameterized Complexity of Eulerian Strong Component Arc Deletion
Václav Blažej, Satyabrata Jana, M. S. Ramanujan +1
In this paper, we study the Eulerian Strong Component Arc Deletion problem, where the input is a directed multigraph and the goal is to delete the minimum number of arcs to ensure…