Source author record

Sudeshna Kolay

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

Data Structures and Algorithms Computational Complexity Computational Geometry

Catalog footprint

Research overview

5works

3topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2020arXiv

Parameterized Study of Steiner Tree on Unit Disk Graphs

We study the Steiner Tree problem on unit disk graphs. Given a $n$ vertex unit disk graph $G$ , a subset $R\subseteq V(G)$ of $t$ vertices and a positive integer $k$ , the objective is to decide if there exists a tree $T$ in $G$ that spans over all vertices of $R$ and uses at most $k$ vertices from $V\setminus R$ . The vertices of $R$ are referred to as terminals and the vertices of $V(G)\setminus R$ as Steiner vertices. First, we show that the problem is NP-Hard. Next, we prove that the Steiner Tree problem on unit disk graphs can be solved in $n^{O(\sqrt{t+k})}$ time. We also show that the Steiner Tree problem on unit disk graphs parameterized by $k$ has an FPT algorithm with running time $2^{O(k)}n^{O(1)}$ . In fact, the algorithms are designed for a more general class of graphs, called clique-grid graphs. We mention that the algorithmic results can be made to work for the Steiner Tree on disk graphs with bounded aspect ratio. Finally, we prove that the Steiner Tree on disk graphs parameterized by $k$ is W[1]-hard.

preprint2015arXiv

A faster FPT Algorithm and a smaller Kernel for Block Graph Vertex Deletion

A graph $G$ is called a \emph{block graph} if each maximal $2$ -connected component of $G$ is a clique. In this paper we study the Block Graph Vertex Deletion from the perspective of fixed parameter tractable (FPT) and kernelization algorithm. In particular, an input to Block Graph Vertex Deletion consists of a graph $G$ and a positive integer $k$ and the objective to check whether there exists a subset $S \subseteq V(G)$ of size at most $k$ such that the graph induced on $V(G)\setminus S$ is a block graph. In this paper we give an FPT algorithm with running time $4^kn^{O(1)}$ and a polynomial kernel of size $O(k^4)$ for Block Graph Vertex Deletion. The running time of our FPT algorithm improves over the previous best algorithm for the problem that ran in time $10^kn^{O(1)}$ and the size of our kernel reduces over the previously known kernel of size $O(k^9)$ . Our results are based on a novel connection between Block Graph Vertex Deletion and the classical {\sc Feedback Vertex Set} problem in graphs without induced $C_4$ and $K_4-e$ . To achieve our results we also obtain an algorithm for {\sc Weighted Feedback Vertex Set} running in time $3.618^kn^{O(1)}$ and improving over the running time of previously known algorithm with running time $5^kn^{O(1)}$ .

preprint2015arXiv

Multivariate Complexity Analysis of Geometric {\sc Red Blue Set Cover}

We investigate the parameterized complexity of GENERALIZED RED BLUE SET COVER (Gen-RBSC), a generalization of the classic SET COVER problem and the more recently studied RED BLUE SET COVER problem. Given a universe $U$ containing $b$ blue elements and $r$ red elements, positive integers $k_\ell$ and $k_r$ , and a family $\F$ of $\ell$ sets over $U$ , the \srbsc\ problem is to decide whether there is a subfamily $\F'\subseteq \F$ of size at most $k_\ell$ that covers all blue elements, but at most $k_r$ of the red elements. This generalizes SET COVER and thus in full generality it is intractable in the parameterized setting. In this paper, we study a geometric version of this problem, called Gen-RBSC-lines, where the elements are points in the plane and sets are defined by lines. We study this problem for an array of parameters, namely, $k_\ell, k_r, r, b$ , and $\ell$ , and all possible combinations of them. For all these cases, we either prove that the problem is W-hard or show that the problem is fixed parameter tractable (FPT). In particular, on the algorithmic side, our study shows that a combination of $k_\ell$ and $k_r$ gives rise to a nontrivial algorithm for Gen-RBSC-lines. On the hardness side, we show that the problem is para-NP-hard when parameterized by $k_r$ , and W[1]-hard when parameterized by $k_\ell$ . Finally, for the combination of parameters for which Gen-RBSC-lines admits FPT algorithms, we ask for the existence of polynomial kernels. We are able to provide a complete kernelization dichotomy by either showing that the problem admits a polynomial kernel or that it does not contain a polynomial kernel unless $\CoNP \subseteq \NP/\mbox{poly}$.

preprint2015arXiv

Parameterized Algorithms for Deletion to (r,l)-graphs

For fixed integers $r,\ell \geq 0$ , a graph $G$ is called an {\em $(r,\ell)$ -graph} if the vertex set $V(G)$ can be partitioned into $r$ independent sets and $\ell$ cliques. This brings us to the following natural parameterized questions: {\sc Vertex $(r,\ell)$ -Partization} and {\sc Edge $(r,\ell)$ -Partization}. An input to these problems consist of a graph $G$ and a positive integer $k$ and the objective is to decide whether there exists a set $S\subseteq V(G)$ ( $S\subseteq E(G)$ ) such that the deletion of $S$ from $G$ results in an $(r,\ell)$ -graph. These problems generalize well studied problems such as {\sc Odd Cycle Transversal}, {\sc Edge Odd Cycle Transversal}, {\sc Split Vertex Deletion} and {\sc Split Edge Deletion}. We do not hope to get parameterized algorithms for either {\sc Vertex $(r,\ell)$ -Partization} or {\sc Edge $(r,\ell)$ -Partization} when either of $r$ or $\ell$ is at least $3$ as the recognition problem itself is NP-complete. This leaves the case of $r,\ell \in \{1,2\}$ . We almost complete the parameterized complexity dichotomy for these problems. Only the parameterized complexity of {\sc Edge $(2,2)$ -Partization} remains open. We also give an approximation algorithm and a Turing kernelization for {\sc Vertex $(r,\ell)$ -Partization}. We use an interesting finite forbidden induced graph characterization, for a class of graphs known as $(r,\ell)$ -split graphs, properly containing the class of $(r,\ell)$ -graphs. This approach to obtain approximation algorithms could be of an independent interest.

preprint2015arXiv

Parameterized Algorithms on Perfect Graphs for deletion to $(r,\ell)$ -graphs

For fixed integers $r,\ell \geq 0$ , a graph $G$ is called an {\em $(r,\ell)$ -graph} if the vertex set $V(G)$ can be partitioned into $r$ independent sets and $\ell$ cliques. The class of $(r, \ell)$ graphs generalizes $r$ -colourable graphs (when $\ell =0)$ and hence not surprisingly, determining whether a given graph is an $(r, \ell)$ -graph is \NP-hard even when $r \geq 3$ or $\ell \geq 3$ in general graphs. When $r$ and $\ell$ are part of the input, then the recognition problem is NP-hard even if the input graph is a perfect graph (where the {\sc Chromatic Number} problem is solvable in polynomial time). It is also known to be fixed-parameter tractable (FPT) on perfect graphs when parameterized by $r$ and $\ell$ . I.e. there is an $f(r+\ell) \cdot n^{\Oh(1)}$ algorithm on perfect graphs on $n$ vertices where $f$ is some (exponential) function of $r$ and $\ell$ . In this paper, we consider the parameterized complexity of the following problem, which we call {\sc Vertex Partization}. Given a perfect graph $G$ and positive integers $r,\ell,k$ decide whether there exists a set $S\subseteq V(G)$ of size at most $k$ such that the deletion of $S$ from $G$ results in an $(r,\ell)$ -graph. We obtain the following results: \begin{enumerate} \item {\sc Vertex Partization} on perfect graphs is FPT when parameterized by $k+r+\ell$ . \item The problem does not admit any polynomial sized kernel when parameterized by $k+r+\ell$ . In other words, in polynomial time, the input graph can not be compressed to an equivalent instance of size polynomial in $k+r+\ell$ . In fact, our result holds even when $k=0$ . \item When $r,\ell$ are universal constants, then {\sc Vertex Partization} on perfect graphs, parameterized by $k$ , has a polynomial sized kernel. \end{enumerate}

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Sudeshna Kolay

Research overview

Is this your work?

5 publications

Parameterized Study of Steiner Tree on Unit Disk Graphs

A faster FPT Algorithm and a smaller Kernel for Block Graph Vertex Deletion

Multivariate Complexity Analysis of Geometric {\sc Red Blue Set Cover}

Parameterized Algorithms for Deletion to (r,l)-graphs

Parameterized Algorithms on Perfect Graphs for deletion to $(r,\ell)$ -graphs

See the researcher in context

Building this map preview

Sudeshna Kolay

Research overview

Is this your work?

5 publications

Parameterized Study of Steiner Tree on Unit Disk Graphs

A faster FPT Algorithm and a smaller Kernel for Block Graph Vertex Deletion

Multivariate Complexity Analysis of Geometric {\sc Red Blue Set Cover}

Parameterized Algorithms for Deletion to (r,l)-graphs

Parameterized Algorithms on Perfect Graphs for deletion to (r,ℓ)(r,\ell)(r,ℓ)-graphs

See the researcher in context

Building this map preview

Parameterized Algorithms on Perfect Graphs for deletion to $(r,\ell)$ -graphs