Publications

    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

    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