9 citations · 15 across the 21 of their papers we have counts for
26 papers
Eccentricity Shortest Path: the structural parameter landscape
Anand Babu, Ashwin Jacob, Hitendra Kumar +1
The Eccentricity Shortest Path problem asks, given a connected graph and a nonnegative integer , whether some shortest path is within distance of every vertex. We study its…
The Complexity of Hamiltonian Cycles and Paths with Prescribed Walk Lengths
Hitendra Kumar, Mathieu Mari, R. B. Sandeep
Fix a set of positive integers. An -Hamiltonian cycle is a cyclic ordering of all vertices of a graph such that each consecutive pair is joined by a walk whose length belong…
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…
Locating a Seymour vertex in oriented graphs having minimum outdegree at most 7
Arpan Sadhukhan, R. B. Sandeep, Sagnik Sen
A vertex of an oriented graph is a Seymour vertex if the number of outneighbors of is less than or equal to the number of second outneighbors of (vertices at direct…
Tight Upper Bounds on Color Reversal by Local Inversions
Hitendra Kumar, Kumud Singh Porte, R. B. Sandeep
A bicoloration of a graph is a map . A local inversion at a vertex complements the subgraph induced by the neighbors of and simultaneously reverse…
A Complexity Dichotomy for Edge Subdivision to -Free Graphs
Marta Piecyk, R. B. Sandeep
For a fixed graph , \HFS\ asks whether at most edge subdivisions can make an input graph contain no induced copy of . We establish a complexity dichotomy for every fixed…
Parameterized algorithms for -Inversion
Dhanyamol Antony, L. Sunil Chandran, Dalu Jacob +1
Inversion of a directed graph with respect to a vertex subset is the directed graph obtained from by reversing the direction of every arc whose endpoints both lie in $Y…
Improved upper bounds on color reversal by local inversions
Kumud Singh Porte, RB Sandeep, Kamal Santra
We study the problem of color reversal in bicolored graphs under local inversions. A \emph{bicoloration} of a graph is a mapping . A \emph{local invers…
Isometric and induced path partitions: a new upper bound and a characterization of some extremal graphs
Irena Penev, R. B. Sandeep, D. K. Supraja +1
An \textit{isometric path} is a shortest path between two vertices. An \textit{isometric path partition} (IPP) of a graph is a set of vertex-disjoint isometric pa…
Erdős-Gyárfás conjecture on graphs without long induced paths
Anand Shripad Hegde, R. B. Sandeep, P. Shashank
Erdős and Gyárfás conjectured in 1994 that every graph with minimum degree at least 3 has a cycle of length a power of 2. In 2022, Gao and Shan (Graphs and Combinatorics) proved th…
Algorithms and complexity for monitoring edge-geodetic sets in graphs
Florent Foucaud, Clara Marcille, R. B. Sandeep +2
A monitoring edge-geodetic set of a graph is a subset of its vertices such that for every edge in the graph, deleting increases the distance between at least one pair o…
Bounds and extremal graphs for monitoring edge-geodetic sets in graphs
Florent Foucaud, Clara Marcille, Zin Mar Myint +3
A monitoring edge-geodetic set, or simply an MEG-set, of a graph is a vertex subset such that given any edge of , lies on every shortest - p…
Switching Classes: Characterization and Computation
Dhanyamol Antony, Yixin Cao, Sagartanu Pal +1
In a graph, the switching operation reverses adjacencies between a subset of vertices and the others. For a hereditary graph class , we are concerned with the maximum…
Algorithms for subgraph complementation to some classes of graphs
Dhanyamol Antony, Sagartanu Pal, R. B. Sandeep
For a class of graphs, the objective of \textsc{Subgraph Complementation to} is to find whether there exists a subset of vertices of the input graph…
Contracting edges to destroy a pattern: A complexity study
Dipayan Chakraborty, R. B. Sandeep
Given a graph G and an integer k, the objective of the -Contraction problem is to check whether there exists at most k edges in G such that contracting them in G results in a gr…
Cutting a tree with Subgraph Complementation is hard, except for some small trees
Dhanyamol Antony, Sagartanu Pal, R. B. Sandeep +1
For a graph property , Subgraph Complementation to is the problem to find whether there is a subset of vertices of the input graph such that modifying by complem…
On subgraph complementation to H-free graphs
Dhanyamol Antony, Jay Garchar, Sagartanu Pal +3
For a class of graphs, the problem SUBGRAPH COMPLEMENT TO asks whether one can find a subset of vertices of the input graph such that complement…
Incompressibility of H-free edge modification problems: Towards a dichotomy
Dániel Marx, R. B. Sandeep
Given a graph and an integer , the -free Edge Editing problem is to find whether there exists at most pairs of vertices in such that changing the adjacency of the…
A Polynomial Kernel for Diamond-Free Editing
Yixin Cao, Ashutosh Rai, R. B. Sandeep +1
An -free editing problem asks whether we can edit at most edges to make a graph contain no induced copy of the fixed graph . We obtain a polynomial kernel for this proble…
Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds
Yixin Cao, R. B. Sandeep
Given an sparse symmetric matrix with nonzero entries, performing Gaussian elimination may turn some zeroes into nonzero values. To maintain the matrix sparse, we would l…
Parameterized Lower Bounds and Dichotomy Results for the NP-completeness of -free Edge Modification Problems
N. R. Aravind, R. B. Sandeep, Naveen Sivadasan
For a graph , the -free Edge Deletion problem asks whether there exist at most edges whose deletion from the input graph results in a graph without any induced copy o…
A cubic vertex kernel for Diamond-free Edge Deletion and more
R. B. Sandeep, Naveen Sivadasan
A diamond is a graph obtained by removing an edge from a complete graph on four vertices. A graph is diamond-free if it does not contain an induced diamond. The Diamond-free Edge D…
Parameterized lower bound and NP-completeness of some -free Edge Deletion problems
N. R. Aravind, R. B. Sandeep, Naveen Sivadasan
For a graph , the -free Edge Deletion problem asks whether there exist at most edges whose deletion from the input graph results in a graph without any induced copy o…
On Polynomial Kernelization of -free Edge Deletion
N. R. Aravind, R. B. Sandeep, Naveen Sivadasan
For a set of graphs , the \textsc{-free Edge Deletion} problem asks to find whether there exist at most edges in the input graph whose deletion result…