RSR. B. Sandeep
R. B. Sandeep
*This is an algorithmically generated author record based on publicly available information.
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Research Subjects
R. B. Sandeep has a total of 5 co-authors. Here are the top co-authors by number of shared publications:
N. R. Aravind
Indian Institute of Technology Hyderabad
3 shared publicationsNaveen Sivadasan
TCS Innovation Labs
3 shared publications- Naveen Sivadasan
TCS Innovation Labs Hyderabad India
2 shared publications - N. R. Aravind
DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING IIT HYDERABAD HYDERABAD INDIA
1 shared publication - Yixin Cao
Department of Computing Hong Kong Polytechnic University Hong Kong China
1 shared publication
Latest Publications
- 23 September 2016
- Published by Springer Nature in Algorithmica
- Vol. 79 (3) , 654-666
On Polynomial Kernelization of $\mathcal {H}$ H -free Edge Deletion- 23 September 2016
- Published by Springer Nature in Algorithmica
- Vol. 79 (3) , 654-666
On Polynomial Kernelization of $\mathcal {H}$ H -free Edge Deletion- Open Access
Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds
Given an $n*n$ sparse symmetric matrix with $m$ nonzero entries, performing Gaussian elimination may turn some zeroes into nonzero values. To maintain the matrix sparse, we would like to minimize the number $k$ of these changes, hence called the minimum fill-in problem. Agrawal et al.~[FOCS'90] developed the first approximation algorithm, based on early heuristics by George [SIAM J Numer Anal 10] and by Lipton et al.~[SIAM J Numer Anal 16]. The objective function they used is $m+k$, the number of nonzero elements after elimination. An approximation algorithm using $k$ as the objective function was presented by Natanzon et al.~[STOC'98]. These two versions are incomparable in terms of approximation. Parameterized algorithms for the problem was first studied by Kaplan et al.~[FOCS'94]. Fomin & Villanger [SODA'12] recently gave an algorithm running in time $2^{O(\sqrt{k} \log k)}+n^{O(1)}$. Hardness results of this problem are surprisingly scarce, and the few known ones are either weak or have to use nonstandard complexity conjectures. The only inapproximability result by Wu et al.~[IJCAI'15] applies to only the objective function $m+k$, and is grounded on the Small Set Expansion Conjecture. The only nontrivial parameterized lower bounds, by Bliznets et al.~[SODA'16], include a very weak one based on ETH, and a strong one based on hardness of subexponential-time approximation of the minimum bisection problem on regular graphs. For both versions of the problem, we exclude the existence of PTASs, assuming P$\ne$NP, and the existence of $2^{O(n^{1-\delta})}$-time approximation schemes for any positive $\delta$, assuming ETH. It also implies a $2^{O(k^{1/2-\delta})} n^{O(1)}$ parameterized lower bound. Behind these results is a new reduction from vertex cover, which might be of its own interest: All previous reductions for similar problems are from some kind of graph layout problems.Open AccessMinimum Fill-In: Inapproximability and Almost Tight Lower Bounds
Given an $n*n$ sparse symmetric matrix with $m$ nonzero entries, performing Gaussian elimination may turn some zeroes into nonzero values. To maintain the matrix sparse, we would like to minimize the number $k$ of these changes, hence called the minimum fill-in problem. Agrawal et al.~[FOCS'90] developed the first approximation algorithm, based on early heuristics by George [SIAM J Numer Anal 10] and by Lipton et al.~[SIAM J Numer Anal 16]. The objective function they used is $m+k$, the number of nonzero elements after elimination. An approximation algorithm using $k$ as the objective function was presented by Natanzon et al.~[STOC'98]. These two versions are incomparable in terms of approximation. Parameterized algorithms for the problem was first studied by Kaplan et al.~[FOCS'94]. Fomin & Villanger [SODA'12] recently gave an algorithm running in time $2^{O(\sqrt{k} \log k)}+n^{O(1)}$. Hardness results of this problem are surprisingly scarce, and the few known ones are either weak or have to use nonstandard complexity conjectures. The only inapproximability result by Wu et al.~[IJCAI'15] applies to only the objective function $m+k$, and is grounded on the Small Set Expansion Conjecture. The only nontrivial parameterized lower bounds, by Bliznets et al.~[SODA'16], include a very weak one based on ETH, and a strong one based on hardness of subexponential-time approximation of the minimum bisection problem on regular graphs. For both versions of the problem, we exclude the existence of PTASs, assuming P$\ne$NP, and the existence of $2^{O(n^{1-\delta})}$-time approximation schemes for any positive $\delta$, assuming ETH. It also implies a $2^{O(k^{1/2-\delta})} n^{O(1)}$ parameterized lower bound. Behind these results is a new reduction from vertex cover, which might be of its own interest: All previous reductions for similar problems are from some kind of graph layout problems. - Open Access
A cubic vertex kernel for Diamond-free Edge Deletion and more
A diamond is a graph obtained by removing an edge from a complete graph on four vertices. A graph is diamond-free if it does not contain an induced diamond. The Diamond-free Edge Deletion problem asks whether there exist at most $k$ edges in the input graph $G$ whose deletion results in a diamond-free graph. For this problem, a polynomial kernel of $O(k^4$) vertices was found by Fellows et. al. (Discrete Optimization, 2011). In this paper, we give an improved kernel of $O(k^3)$ vertices for Diamond-free Edge Deletion. Further, we give an $O(k^2)$ vertex kernel for a related problem {Diamond,K_t}-free Edge Deletion, where $t\geq 4$ is any fixed integer. To complement our results, we prove that these problems are NP-complete even for $K_4$-free graphs and can be solved neither in subexponential time (i.e., $2^{o(|G|)}$) nor in parameterized subexponential time (i.e., $2^{o(k)}\cdot |G|^{O(1)}$), unless Exponential Time Hypothesis fails. Our reduction implies the hardness and lower bound for a general class of problems, where these problems come as a special case.Open AccessA cubic vertex kernel for Diamond-free Edge Deletion and more
A diamond is a graph obtained by removing an edge from a complete graph on four vertices. A graph is diamond-free if it does not contain an induced diamond. The Diamond-free Edge Deletion problem asks whether there exist at most $k$ edges in the input graph $G$ whose deletion results in a diamond-free graph. For this problem, a polynomial kernel of $O(k^4$) vertices was found by Fellows et. al. (Discrete Optimization, 2011). In this paper, we give an improved kernel of $O(k^3)$ vertices for Diamond-free Edge Deletion. Further, we give an $O(k^2)$ vertex kernel for a related problem {Diamond,K_t}-free Edge Deletion, where $t\geq 4$ is any fixed integer. To complement our results, we prove that these problems are NP-complete even for $K_4$-free graphs and can be solved neither in subexponential time (i.e., $2^{o(|G|)}$) nor in parameterized subexponential time (i.e., $2^{o(k)}\cdot |G|^{O(1)}$), unless Exponential Time Hypothesis fails. Our reduction implies the hardness and lower bound for a general class of problems, where these problems come as a special case. - 9 December 2015
- Published by Springer Nature
- p. 424-438
Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems
- 9 December 2015
- Published by Springer Nature
- p. 424-438
Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems
- 3 December 2014
- Published by Springer Nature
- p. 28-38
On Polynomial Kernelization of $\mathcal {H}$-free Edge Deletion- 3 December 2014
- Published by Springer Nature
- p. 28-38
On Polynomial Kernelization of $\mathcal {H}$-free Edge Deletion