Author name cluster

Deepak Rajendraprasad

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.

3 papers

2 author rows

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

SODA Conference 2017 Conference Paper

Testing for Forbidden Order Patterns in an Array

Ilan Newman
Yuri Rabinovich
Deepak Rajendraprasad
Christian Sohler

In this paper, we study testing of sequence properties that are defined by forbidden order patterns. A sequence f: {1, …, n} → ℝ of length n contains a pattern is the group of permutations of k elements), iff there are indices i 1 < i 2 < · · · < i k, such that f (i x ) > f (i y ) whenever π(χ) > π( y ). If f does not contain π, we say f is π-free. For example, for π = (2, 1), the property of being π-free is equivalent to being non-decreasing, i. e. monotone. The property of being ( k, k — 1, …, 1)-free is equivalent to the property of having a partition into at most k - 1 non-decreasing subsequences. Let k constant, be a (forbidde n ) pattern. Assuming f is stored in an array, we consider the property testing problem of distinguishing the case that f is π-free from the case that f differs in more than en places from any π-free sequence. We show the following results: There is a clear dichotomy between the monotone patterns and the non-monotone ones: For monotone patterns of length k, i. e. , ( k, k - 1, …, 1) and (1, 2, …, k ), we design non-adaptive one-sided error ε-tests of (∊ −1 log n ) O ( k 2 ) query complexity. For non-monotone patterns, we show that for any size- k non-monotone π, any non-adaptive one-sided error ε-test requires at least Ω(γ / η) queries. This general lower bound can be further strengthened for specific non-monotone k -length patterns to Ω( n 1–2/( k +1) ). On the other hand, there always exists a non- adaptive one-sided error ε-test for with O(e −1/k n 1–1/k ) query complexity Again, this general upper bound can be further strengthened for specific non-monotone patterns. E. g. , for π = (1, 3, 2), we describe an ε-test with (almost tight) query complexity of Finally, we show that adaptivity can make a big difference in testing non-monotone patterns, and develop an adaptive algorithm that for any tests π-freeness by making (∊ −1 logn) O(1) queries. For all algorithms presented here, the running times are linear in their query complexity.

Details

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