Academics

    Constant-Factor Approximation Algorithms for Convex Cover and Hidden Set in a Simple Polygon

    Consider a simple polygon P. What is the minimum number of convex subsets of P are required to completely cover P? This fundamental problem (called Convex Cover) in computational geometry has proven to be frustratingly hard to solve exactly and/or to approximate for over fifty years. In this work, we provide the first constant-factor approximation for Convex Cover. This algorithm runs in (nearly) quadratic time. En route, we also provide a constant-factor approximation algorithm for the Hidden Set problem, where we need to find the maximum number of points inside P which do not see each other. This is the first approximation algorithm for Hidden Set in literature.

    posted in Academics Publications on by Prahlad Narasimhan

    Dominator Coloring Parameterized by Cluster Vertex Deletion Number

    Given a simple graph G and a natural number l, Dominator Coloring asks if it possible to properly color G with at most l colors such that for every vertex v in the graph, there exists a color class c where every vertex colored c is in the neighborhood of v. This problem, first described in 2006 and studied in several papers since then, hosts several interesting open problems. In this combined work (with Prof Aritra Banik and Prof Venkatesh Raman), we initiate the study of the problem through the lens of structural parameterization. We prove that Dominator Coloring, parameterized by the input graph's Cluster Vertex Deletion number, is FPT. We also design faster, simpler, and randomized parameterized algorithms when the parameter is a special CVD set.

    posted in Academics Publications on by Prahlad Narasimhan

    The Four-Colour Theorem

    The Four-Colour Theorem, first conjectured in 1852, states that any planar graph can be properly coloured with four colours. The theorem was eventually proved 120 years later by Kenneth and Appel. This proof was considered to be a watershed moment in Mathematics. Why? Because it used computers.

    posted in Academics Presentations on by Prahlad Narasimhan

    Geometric Hitting Set Problems

    A Local Search algorithm, for a maximization problem, works as follows - start with a small set which satisfies the required property; check if there is a "small" subset of it can be swapped with a "slightly larger" set so that the remaining set still satisfies this property; swap if possible and repeat the procedure or return the set that is obtained. For my 8th and 9th semester projects, I worked on this algorithm when applied to the geometric setting. I wrote a report that discusses the construction of a PTAS using this paradigm and its optimality in certain conditions.

    posted in Academics Reports on by Prahlad Narasimhan

    One-Sided Terrain Guarding and Chordal Graphs

    This is the journal version of my previous work (covered in this blog post) on the Terrain Guarding Problem. This extends results of the conference version of the paper to the Continuous Terrain Guarding Problem and to a version of the Dominating Set Problem in terrain-like graphs. Moreover, it significantly shortens the proof of one of the theorems and corrects some small errors present in the previous version.

    posted in Academics Publications on by Prahlad Narasimhan

    One-Sided Discrete Terrain Guarding and Chordal Graphs

    The Discrete Terrain Guarding problem (discussed in one of my previous posts) has been shown to be NP-Hard, but it remains to be seen if it is FPT with respect to the size of the solution size. In this direction, Ashok et al. proved in 2015 that Orthogonal Discrete Terrain Guarding is FPT. They used a lemma proved by Katz and Roisman which established a relationship between this problem and the Clique Cover problem in chordal graphs. My (first!) paper extends this lemma and takes a step forward in understanding the fixed-parameterized tractability of Discrete Terrain Guarding.

    posted in Academics Publications on by Prahlad Narasimhan

    Linear and Semidefinite Programming

    Optimization has a very simple premise - you want to maximize or minimize something with respect to a bunch of constraints. In Linear Programming, we further restrict our study to the case where the constraints are also linear and the condition imposed on each of these functions is that they must be at most a fixed value. In Semidefinite Programming, we impose another restriction - the matrix described by the variables must be positive (that is, it must be both positive semidefinite and self-adjoint or, equivalently, it must be a matrix whose eigenvalues are positive reals). For my 7th semester math project, I wrote a report that discusses these two optimiization constructs. The report assumes literacy in basic algorithms, linear algebra and (a tiny bit of) probability.

    posted in Academics Reports on by Prahlad Narasimhan

    Annihilators of Banach Spaces

    As part of my course on Functional Analysis in my 7th semester, I was required to present a topic that was an extension of the course. I chose to read up on annihilators of Banach spaces and characterize the conditions required for the sum of two closed subspaces of a Banach space to be closed. You know, just because.

    posted in Academics Reports on by Prahlad Narasimhan

    Colouring a Sequence of Boxes

    One of my friends was applying to Google for a job and got this problem in one of the final written rounds. This was a fun little problem that helped me procrastinate...

    posted in Academics Problems on by Prahlad Narasimhan

    Some Problems in Linear Algebra

    I came across a couple of fun problems when I was going through "Linear Algebra Done Right" by Axler. I really enjoyed this book and it was great for a "second reading" of the basics of Linear Algebra.

    posted in Academics Problems on by Prahlad Narasimhan

    Terrain Guarding

    The Terrain Guarding problem is a variation of the Art Gallery problem - you are given a polygonal chain and are required to find the minimum number of vertices on it to guard a given set of points on the chain. It turns out that this is a hard computational problem. During my quest to understand this paper by Ashok et al., I picked up a few more concepts and decided to write a report which seeks to let anyone who has done a basic course in algorithms understand (almost) current research in this topic. This eventually let to my first publication.

    posted in Academics Reports on by Prahlad Narasimhan

    Kleene Algebra

    While following "Automata and Computability" by D.C Kozen during my first summer internship at CMI, I came across a supplementary lecture on Kleene Algebras. When I came back to it a semester later, I discovered that the number of axioms required to define this algebra can be reduced by one.

    posted in Academics Reports on by Prahlad Narasimhan