Author name cluster

Jasine Babu

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

6 papers

1 author row

TCS Journal 2025 Journal Article

Arborescences and shortest path trees when colors matter

P.S. Ardra
Jasine Babu
Kritika Kashyap
R. Krithika
Sreejith K. Pallathumadam
Deepak Rajendraprasad

We are given an edge-colored (directed or undirected) graph and our objective is to find a specific type of subgraph, like a spanning tree, an arborescence, a single-source shortest path tree, a perfect matching etc. , with constraints on the number of edges of each color. Some of these problems, like color-constrained spanning tree, have elegant solutions and some of them, like color-constrained perfect matching, are longstanding open questions. In this work, we study color-constrained arborescences and shortest path trees. Computing a color-constrained shortest path tree on weighted digraphs turns out to be NP -hard in general but polynomial-time solvable when all cycles have positive weight. This polynomial-time solvability is due to the fact that the solution space is essentially the set of all color-constrained arborescences of a directed acyclic subgraph of the original graph. While finding color-constrained arborescences of digraphs is NP -hard in general, we give an efficient algorithm when the input digraph is acyclic. Consequently, a color-constrained shortest path tree on weighted digraphs having only positive weight cycles can be efficiently computed. Our algorithm generalizes to the problem of finding a color-constrained shortest path tree with the minimum total weight. Both our algorithms use a single source shortest path algorithm and a (minimum cost) maximum flow algorithm as subroutines. By using the recent algorithm by van den Brand et al. (FOCS 2023) for these subroutines, our algorithms achieve near-linear running time when the edge weights are integral and polynomially-bounded in the size of the graph. En route, we sight nice connections to colored matroids and color-constrained bases. In fact, our approach can be adapted to find a largest common independent set of two generalized partition matroids in near-linear time.

Details DOI

TCS Journal 2025 Journal Article

Computing eternal vertex cover number of maximal outerplanar graphs in linear time

Jasine Babu
K. Murali Krishnan
Veena Prabhakaran
Nandini J. Warrier

Eternal vertex cover problem is a variant of the classical vertex cover problem modeled as a two player attacker-defender game. Computing the eternal vertex cover number of graphs is known to be NP-hard in general and even for bipartite graphs. There is a quadratic complexity algorithm known for this problem for chordal graphs. Maximal outerplanar graphs form a subclass of chordal graphs, for which no algorithm of sub-quadratic time complexity is known. In this paper, we obtain a linear time recursive algorithm for computing eternal vertex cover number of maximal outerplanar graphs.

Details DOI

TCS Journal 2021 Journal Article

A substructure based lower bound for eternal vertex cover number

Jasine Babu
Veena Prabhakaran
Arko Sharma

The eternal vertex cover (EVC) problem is to compute the minimum number of guards to be placed on the vertices of a graph so that any sequence of attacks on its edges can be defended by dynamically reconfiguring the guards. The problem is NP-hard in general and polynomial time algorithms are unknown even for simple graph classes like cactus graphs and bipartite graphs. A major difficulty is that only few lower bounds, other than the trivial lower bound of vertex cover, is known in general and the known bounds are too weak to yield useful results even for the graph classes mentioned above. We introduce the notion of substructure property in the context of the EVC problem and derive a new lower bounding technique for the problem based on the property. We apply the technique to cactus graphs and chordal graphs and obtain new algorithms for solving the eternal vertex cover problem in linear time for cactus graphs and quadratic time for a family of graphs that includes all chordal graphs and cactus graphs.

Details DOI

TCS Journal 2020 Journal Article

A local characterization for perfect plane near-triangulations

Sameera M. Salam
Jasine Babu
K. Murali Krishnan

We derive a local criterion for a plane near-triangulated graph to be perfect. It is shown that a plane near-triangulated graph is perfect if and only if it does not contain either a vertex, an edge or a triangle, the neighbourhood of which has an odd hole as its boundary. The characterization leads to an O ( n 2 ) algorithm for checking perfectness of plane near-triangulations.

Details DOI

TCS Journal 2014 Journal Article

2-Connecting outerplanar graphs without blowing up the pathwidth

Jasine Babu
Manu Basavaraju
L. Sunil Chandran
Deepak Rajendraprasad

Given a connected outerplanar graph G of pathwidth p, we give an algorithm to add edges to G to get a supergraph of G, which is 2-vertex-connected, outerplanar and of pathwidth O ( p ). This settles an open problem raised by Biedl [1], in the context of computing minimum height planar straight line drawings of outerplanar graphs, with their vertices placed on a two-dimensional grid. In conjunction with the result of this paper, the constant factor approximation algorithm for this problem obtained by Biedl [1] for 2-vertex-connected outerplanar graphs will work for all outer planar graphs.

Details DOI

TCS Journal 2014 Journal Article

Fixed-orientation equilateral triangle matching of point sets

Jasine Babu
Ahmad Biniaz
Anil Maheshwari
Michiel Smid

Given a point set P and a class C of geometric objects, G C ( P ) is a geometric graph with vertex set P such that any two vertices p and q are adjacent if and only if there is some C ∈ C containing both p and q but no other points from P. We study G ▽ ( P ) graphs where ▽ is the class of downward equilateral triangles (i. e. , equilateral triangles with one of their sides parallel to the x-axis and the corner opposite to this side below that side). For point sets in general position, these graphs have been shown to be equivalent to half- Θ 6 graphs and TD-Delaunay graphs. The main result in our paper is that for point sets P in general position, G ▽ ( P ) always contains a matching of size at least ⌈ | P | − 1 3 ⌉ and this bound is tight. We also give some structural properties of G ✡ ( P ) graphs, where ✡ is the class which contains both upward and downward equilateral triangles. We show that for point sets in general position, the block cut point graph of G ✡ ( P ) is simply a path. Through the equivalence of G ✡ ( P ) graphs with Θ 6 graphs, we also derive that any Θ 6 graph can have at most 5 n − 11 edges, for point sets in general position.

Details DOI