| Research Interests | | Publications | | Students Advised | | Professional Activities | | Contact | |

Venkatesh Raman Theoretical Computer Science Institute of Mathematical Sciences |

Brief Resume [pdf]

Succinct (Space Efficient) Data Structures

Algorithms for satisfiability

Sorting and Selection and related problems

V. Raman and S. Saurabh

Algorithmica 64(1) (2012) and 65(4), 2013.

Space-Efficient Data Structures, Streams and Algorithms, Ian Munro Festschrift

Andrej Brodnik, Alejandro Lopez-Ortiz, Venkatesh Raman and Alfredo Viola

Springer Verlag LNCS 8066 (August 2013).

Proceedings of the 5th IPEC (International Symposium on Parameterized and Exact Computation) Symposium

V. Raman and S. Saurabh

Springer Verlag LNCS 6478 (December 2010).

Proceedings of the 19th FST and TCS Conference

C Pandu Rangan, V. Raman and R Ramanujam

Springer Verlag LNCS 1738 (December 1999).

Selected Publications in Data Structures, Parameterized and Exact Computation, Selection and Sorting and Satisfiability .

Kernel lower bounds using co-nondeterminism: Finding induced hereditary subgraphs Stefan Kratsch, Marcin Pilipczuk, Ashutosh Rai and Venkatesh Raman accepted in SWAT 2012. Parameterized Algorithms for Even Cycle Transversal P. Misra, V. Raman, M. S. Ramanujan and S. Saurabh accepted in WG 2012. LP can be a cure for parameterized problems N. S. Narayanaswamy, V. Raman, M.S. Ramanujan and S. Saurabh accepted in STACS 2012. A polynomial kernel for feedback arc set in bipartite tournaments P. Misra, V. Raman, M. S. Ramanujan, S. Saurabh accepted in ISAAC 2011. On Parameterized Independent Feedback Vertex Set N. Misra, G. Philip, V. Raman and S. Saurabh, Proceedings of COCOON 2011, 98-109. Paths, Flowers and Vertex Cover V. Raman, M. S. Ramanujan and S. Saurabh, Proceedings of ESA 2011, 382-393. Bidimensionality and EPTAS [pdf] F. Fomin, D. Lokshtanov, V. Raman and S. Saurabh, Proceedings of ACM-SIAM symposium on Discrete Algorithms (SODA) 2011. The effect of Girth on the Kernalization Complexity of Connected Dominating Set [pdf], N. Misra, G. Philip, V. Raman and S. Saurabh, Proceedings of FSTTCS 2010: 96-107. Lower Bounds for Kernalization [pdf], N. Misra, V. Raman and S. Saurabh, Discrete Optimization 8(1): 110-128 (2011). Fast Local Search Algorithms for Weighted Feedback Arc Set in Tournaments [pdf], F. Fomin, D. Lokshtanov, V. Raman and S. Saurabh, in the Proceedings of Conference on Artificial Intelligence (AAAI 2010). A Quartic Kernel for Pathwidth-One Vertex Deletion [pdf], G. Philip, V. Raman and Y. Villanger, in the Proceedings of Graph Theoretic Concepts in Computer Science, WG 2010: 196-207. Solving Minones 2SAT as fast as Vertex Cover [pdf], N. Misra, N. Narayanaswamy, V. Raman and Balsri Shankar, in the proceedings of Mathematical Foundations of Computer Science (MFCS) 2010: 549-555. Fixed-parameter Algorithms for Cochromatic Number and Disjoint Rectangle Stabbing [pdf], P. Heggernes, D. Kratsch, D. Lokshtanov, V. Raman and S. Saurabh, in the proceedings of the Scandinavian Workshop on Algorithm Theory (SWAT) 2010: 334-345. Beyond Bidimensionality: Parameterized Subexponential Algorithms on Directed Graphs [pdf], F. Fomin, F. Horn, D. Lokshtanov, V. Raman and S. Saurabh in the proceedings of the Symposium on Theoretical Aspects of Computer Science (STACS) 2010: 251-262. FPT Algorithms for Connected Feedback Vertex Set [pdf], N. Misra, G. Philip, V. Raman, S. Saurabh and S. Sikdar, in the Proceedings of Workshop on Algorithms and Computation (WALCOM) 2010; expanded version in the Journal of Combinatorial Optimization (April 2011) 1-16.. Subexponential Algorithms for Partial Cover Problems [pdf], F. Fomin, D. Lokshtanov, V. Raman and S. Saurabh, Information Processing Letters 111(16):814-818 (2011), preliminary version in the proceedings of FSTTCS 2009 Conference. The Complexity of Konig Subgraph Problems and Above-Guarantee Vertex Cover [pdf] S. Mishra, V. Raman, S. Saurabh, S. Sikdar and C. R. Subramanian, Algorithmica (May 2010). Preliminary versions appeared in the Proceedings of ISAAC 2007 and ISAAC 2008 symposiums. On the Directed degree-preserving spanning tree problem [pdf], D. Lokshtnov, V. Raman, S. Saurabh and S. Sikdar, Discrete Optimization 8(1): 97-109 (2011), preliminary version in the Proceedings of IWPEC 2009. The Budgeted Unique Coverage Problem and Color-Coding [pdf], N. Mishra, V. Raman, S. Saurabh and S. Sikdar, Proceedings of the 4th International Computer Science Symposium in Russia (CSR) 2009. Solving Dominating Set in Larger Class of Graphs -- FPT algorithms and Polynomial Kernels [pdf], G. Philip, V. Raman, S. Sikdar Proceedings of the ESA 2009, expanded version accepted in a journal Parameterizing Algorithms for Generalized Domination, V. Raman, S. Saurabh, S. Srihari, Proceedings of COCOA 2008, Springer LNCS 5165, pages 116-126. Parameterized Complexity of the Induced Subgraph problem in directed graphs [pdf] V. Raman and S. Sikdar, Information Processing Letters 104 (2007) 79-85 Improved FPT algorithms for two edge problems --MaxCut and MaxDag [pdf] V. Raman and S. Saurabh, Information Processing Letters 104 (2007) 65-72 Parameterized Complexity of the Unique Coverage Problem, H. Moses, V. Raman and S. Sikdar, Proceedings of the 18th International Symposium on Algorithms and Computation (ISAAC 2007), Springer LNCS 4835, pages 621-631. Exact and Parameterized Algorithms through (old and new) Structural Graph theoretical Results V. Raman and S. Saurabh In the proceedings of the International Conference on Discrete Mathematics (2006), Pages 177-189. Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems [pdf] S. Gupta, V. Raman and S. Saurabh 26th Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2006).Kolkata, India, December 13-15, 2006. Parameterizing above or below guaranteed values M. Mahajan and V. Raman and S. Sikdar Journal of Computer and System Sciences 75(2):137-153 (2009). (Preliminary version as 'Parameterizing MAXSNP problems above Guaranteed Values' [pdf] in Proceedings of 2nd International Workshop on Parameterized and Exact Computation IWPEC'06, 13 - 15 Sep, 2006, Zuerich (Switzerland). (part of ALGO 2006) . Springer-Verlag Lecture Notes in Computer Science series Volume 4169 pp 38--49.) Short Cycles make W-hard problems hard; FPT algorithms for W-hard problems in Graphs with no short cycles [pdf] V. Raman and S. Saurabh Algorithmica 52(2):203-225 (2008). (Preliminary version as `Triangles, 4-Cycles and Parameterized (In-) Tractability in the proceedings of 10th Scandinavian Workshop on Algorithmic Theory SWAT, LNCS 4051, 304-315 (2006).) Faster Fixed Parameter Tractable Algorithms for Finding Feedback Vertex Sets [pdf] V. Raman, S. Saurabh and C. R. Subramanian ACM Transactions on Algorithms (TALG) 2 (3) 403-415 (July 2006). (Preliminary versions in ISAAC 2002 and GRACO 2004). Parameterized Algorithms for Feedback Set Problems and Their Duals in Tournaments [pdf] V. Raman and S. Saurabh Theoretical Computer Science (TCS). Volume 351, Issue 3, Pages 446-458 (2006) (Invited Paper of Ist International Workshop on Parameterized and Exact Computation) Efficient Exact Algorithms through Enumerating Maximal Independent Sets and Other Techniques [ps] V. Raman , S. Saurabh and S.Sikdar in `Theory of Computing Systems' 41(30:563-587 (2007). (Preliminary version of the paper appeared as 'Improved Exact Exponential Algorithms for Vertex Bipartization and Other Problems'[pdf] In the proccedings of 9th Italian Conferenece on Theoretical Computer Science, ICTCS, LNCS 3701, 375-389 (2005)) Parameterized Complexity of Finding Hereditary Properties [pdf] S. Khot and V. Raman. Theoretical Computer Science 289 (2002) 997-1008. Approximation Algorithms for some Parameterized Counting Problems [pdf] V. Arvind and V. Raman. Electronic Colloquium on Computational Complexity, 31 (2002). Proceedings of ISAAC 2002 Springer LNCS 2518 453-464. The Complexity of irredundant sets parameterized by size [pdf] R. G. Downey, M. R. Fellows and V. Raman. Discrete Applied Mathematics 100 (2000) 155-167. An Improved Fixed Parameter Algorithm for Vertex Cover R. Balasubramanian, M. Fellows and V. Raman. Information Processing Letters, 65 (1998) 163 -168 Parameterized Complexity V. Raman. in Proceedings of the 7th National Seminar on Theoretical Computer Science, June 1997, (Chennai, India) I-1 to I-18.

Succinct Representation of Equivalence classes M. Lewenstein, I. Munro and V. Raman to appear in the proceedings of ISAAC 2013. Less space: Indexing for Queries with Wildcards M. Lewenstein, I. Munro, V. Raman and S. Thankacchan to appear in the procedings of ISAAC 2013. Succinct Representations of Permutations and Functions J.I. Munro, R. Raman, V. Raman, S. S. Rao. Theoretical Computer Science (2012) 74-88. CoRR abs/1108.4501:(2011) preliminary version in Proceedings of ICALP 2003 (Springer LNCS 2719, 345-.) [pdf] Succinct ordinal trees with level-ancestor queries [pdf] R. F. Geary, R. Raman and V. Raman ACM Transactions on Algorithms 2 (2006), pp. 510-534. SODA '04 special issue, J. I. Munro and A. Lopez-Ortiz, eds. A simple optimal representation for balanced parentheses [pdf] R. F. Geary, N. Rahman, R. Raman and V. Raman Theoretical Computer Science 368 (2006), pp. 231-246. CPM '04 special issue, U. Dogrusoz, S. Muthukrishnan and S. C. Sahinalp, eds. Representing trees of higher degree [pdf] D. Benoit, E. D. Demaine, J. I. Munro, R. Raman, V. Raman and S. S. Rao Algorithmica, 43 (2005), pp. 275-292. Succinct Indexable Dictionaries with Applications to representations of k-ary trees and multisets [pdf] Rajeev Raman, V. Raman and S. Srinivasa Rao. in ACM Transactions on Algorithms 3(4) (2007), preliminary version in Proceedings of ACM-SIAM conference of Discrete Algorithms (SODA) 2002. Representing Dynamic Trees Succinctly J. I. Munro, V. Raman and Adam Storm. Proceedings of ACM-SIAM conference of Discrete Algorithms (SODA) 2001. A tradeoff between search and update in dictionaries J. Radhakrishnan and V. Raman. Information Processing Letter 80 (2001) 243-247. Succinct Dynamic Data Structures [pdf] R. Raman, V. Raman, S. S. Rao Proceedings of WADS 2001. Explicit Deterministic Construction for Membership in the Bitprobe Model [pdf] J. Radhakrishnan, V. Raman and S. S. Rao Proceedings of ESA 2001. Space Efficient Suffix Trees [pdf] J.I. Munro, V. Raman and S. Srinivasa Rao. Journal of Algorithms 39 (2) (2001) 205-222. Succinct Representation of Balanced Parentheses and Static Trees J. I. Munro and V. Raman. 1997 IEEE Symposium on Foundations of Computer Science: 118-126 SIAM J. Computing, Vol. 31, No.3 (2001) 762-776. Static Dictionaries Supporting Rank [pdf] V. Raman and S. S. Rao. Proceedings of ISAAC 99 (Springer LNCS 1741) 18-26. Path Balance Heuristic for Self-Adjusting Binary Search Trees R. Balasubramanian and Venkatesh Raman FSTTCS 1995: 338-348.

Sorting and Selection in Restore Model T. M. Chan, I. Munro and V. Raman to appear in the procedings of SODA 2014. Faster, space efficient selection for integers in read-only memory T. M. Chan, J. I. Munro and V. Raman to appear in the proceedings of ISAAC 2013. Approximate Block Sorting [ps] M. Mahajan and R. Rama and V. Raman and S. Vijayakumar. International Journal of Foundations of Computer Science Volume 17(2) (April 2006), pp. 337--355. On the pseudoachromatic number of join of graphs R Balasubramanian, V. Raman V. Yegnanarayanan International Journal of Computer Mathematics Vol 80 No. 9 pages 1131-1137 (Sept 2003) Improved Upper Bounds for Time-Space Tradeoffs for Selection V. Raman and S. Ramnath. Nordic Journal of Computing 6 (1999) 162-180. Selecting small ranks in EREW PRAM S. Ramnath and V. Raman. Information Processing Letters 71 (1999) 183-186. Finding Generalized Hamiltonian paths in Tournaments Proceedings of the conference on Graph Connections(1999) Finding Scores in Tournaments R. Balasubramanian, V. Raman and G. Srinivasaraghavan. Journal of Algorithms 24 (1997) 380-394. Selection from Read-Only Memory and Sorting with minimum Data Movement J. I. Munro and V. Raman. Theoretical Computer Science 165 (1996) 311-323. Fast Stable In-Place Sorting with O(n) Data Moves J. I. Munro and Venkatesh Raman Algorithmica 16(2):151-160 (1996). Sorting Multisets and Vectors In-Place J. I. Munro and Venkatesh Raman WADS 1991: 473-480. Stable in situ sorting and minimum data movement J. I. Munro, V. Raman, J.S. Salowe BIT 30(1990) 220-234 Sorting with Minimum Data Movement J. I. Munro and V. Raman Journal of Algorithms 13(3) (1992)

Solving min ones 2-sat as fast as vertex cover Neeldhara Misra, N. S. Narayanaswamy, Venkatesh Raman, Bal Sri Shankar Theoretical Computer Science 506: 115-121 (2013). Improved Fixed-Parameter Algorithm for the Minimum Weight 3-SAT problem Venkatesh Raman and Bal Sri Shankar Proceedings of WALCOM 2013: 265-273. Upper and Lower Bounds for Weak Backdoor Set Detection Neeldhara Misra, Sebastian Ordyniak, Venkatesh Raman, Stefan Szeider Proceedings of SAT 2013. Fixed-parameter tractability of satisfying beyond the number of variables R. Crowston, G. Gutin, M. Jones, V. Raman, S. Saurabh and A. Yeo proceedings of SAT 2012. Parameterized Complexity of MaxSat Above Average R. Crowston, G. Gutin, M. Jones, V. Raman and S. Saurabh CORR abs/1108.4501:(2011) in proceedings of LATIN 2012. Upper Bounds for MaxSat: Further Improved [ps] N. Bansal and V. Raman. Proceedings of ISAAC 99 (Springer LNCS 1741) 247-258. Parameterizing Above the Guarantee: MAXSAT and MAXCUT [ps] M. Mahajan and V. Raman. Journal of Algorithms 31 (1999) 335-354. A Simplified NP-Complete MAXSAT Problem [pdf] V. Raman, B. Ravikumar and S. Srinivasa Rao. Information Processing Letters 65 (1998) 1-6.## Students Advised

PhD Students

S Srinivasa Rao

Thesis : Succinct Data Structures (2002)

Saket Saurabh

Thesis: Exact Algorithms for Optimization and Parameterized Versions of some graph theoretic problems (2008)

(the following three jointly supervised with Saket Saurabh)

Somnath Sikdar

Thesis: Parameterizing from the extremes -- feasible parameterizations of some NP hard Optimization Problems (June 2010)

Geevarghese Philip

Thesis: The kernelization complexity of some domination and covering problems (September 2011)

Neeldhara Misra

Thesis: Kernels for the F-Deletion problem (September 2011)

Master's Students

S V Nagaraj

Thesis : Optimal Binary Search Trees

April 1994

S Srinivasa Rao

Thesis : A survey of Approximation Algorithms for the Maximum Satisfiability Problem

April 1997

G Srinivasan (Anna University)

Thesis : Self Adjusting Binary Search Trees

May 1998

V Reemus Kumar (Madurai Kamaraj University)

Thesis : Implicit Data Structures for Multikey Search Problem and implementing Rank and Select in a Bit vector

May 2002

R Ramani (REC Trichy)

Thesis : Implementation of Rank and Select and other succinct strutures

June 2003

Geevarghese Philip

Thesis: Fixed-Parameter Algorithms for Graph Problems Using Graph Minor Theory

April 2008

Neeldhara Misra

Thesis: Infeasibility of Polynomial Kernelization

April 2009

Varun Kumar Jayapal (Chennai Mathematical Institute)

Thesis: Finding and Maintaining medians under various constraints

July 2013

Abhishek H. Dang (Chennai Mathematical Institute)

Thesis: Lower bound techniques for dynamic data structures

July 2013

## Professional Activities

- Program Committee member of FAW 2014, STACS 2014, SWAT 2014, IPEC 2013, WALCOM 2012, SPIRE 2011, IPEC 2010 (Co-chair), CATS 2010, TAMC 2009, IWPEC 2006, TCS 2002, FST TCS 2002, 1999 (Co-chair), 1997 and 1996.

- Member of the council of Indian Association for Research in Computing Science (IARCS) 2002-2005

- Member of IWPEC steering committee (2006-2010)

- Organizing Committee member of the FST & TCS 1998 Conference

## Personal Information

Address (Home) Plot 3 and 4, Gomathinagar,

Ramnagar 8th Street ,

Ramnagar North Extension,

Velacheri,

Chennai 600 042. India.Telephone (IMSc) (044) 2254 1856, 2254 3220 Telephone (Home) (044) 4207 4853 FAX (IMSc) (044) 2254 1586