Krithika Ramaswamy

Welcome to my homepage - I am a post doctoral researcher at the Theoretical Computer Science group of the Institute of Mathematical Sciences, Chennai. I completed my PhD at the Indian Institute of Technology Madras. I work in the areas of parameterized and approximation algorithms for graph theoretic problems. 

Email:  reachkrithiks@gmail.com


Journal Publications
  • Revisiting Connected Vertex Cover: FPT Algorithms and Lossy Kernels [Theory of Computing Systems 2018] (co-authored with Diptapriyo Majumdar and Venkatesh Raman)
  • Dynamic Parameterized Problems [Algorithmica 2017] (co-authored with Abhishek Sahu and Prafullkumar Tale)
  • Approximability of Clique Transversal in Perfect Graphs [Algorithmica 2017] (co-authored with Samuel Fiorini, N.S. Narayanaswamy and Venkatesh Raman)
  • Parameterized Algorithms for (r,l)-Partization [Journal of Graph Algorithms and Applications 2013] (co-authored with N.S.Narayanaswamy)
  • Another Disjoint Compression Algorithm for Odd Cycle Transversal [Information Processing Letters 2013] (co-authored with N.S.Narayanaswamy)
  • A Dirac-type Characterization of k-chordal Graphs [Discrete Mathematics 2013] (co-authored with Rogers Mathew, N.S.Narayanaswamy and N.Sadagopan) 

Conference Publications

  • The Parameterized Complexity of Cycle Packing: Indifference is Not an Issue [LATIN 2018] (co-authored with Abhishek Sahu, Saket Saurabh and Meirav Zehavi)
  • On the Parameterized Complexity of Simultaneous Deletion Problems [FSTTCS 2017] (co-authored with Akanksha Agrawal, Daniel Lokshtanov, Amer Mouawad and M. S. Ramanujan)
  • Parameterized and Exact Algorithms for Class Domination Coloring [SOFSEM 2017] (co-authored with Ashutosh Rai, Saket Saurabh, and Prafullkumar Tale)
  • Lossy Kernels for Graph Contraction Problems [FSTTCS 2016] (co-authored with Pranabendu Misra, Ashutosh Rai and Prafullkumar Tale)
  • Dynamic Parameterized Problems [IPEC 2016] (co-authored with Abhishek Sahu and Prafullkumar Tale) 
    • Excellent Student Paper Award.
  • LP Approaches to Improved Approximation for Clique Transversal in Perfect Graphs [European Symposium on Algorithms 2014] (co-authored with Samuel Fiorini, N.S. Narayanaswamy and Venkatesh Raman)
  • Generalized Above Guarantee Vertex Cover and r-Partization [Workshop on Algorithms and Computation 2012] (co-authored with N.S.Narayanaswamy)

Education

Ph.D. [2012 - 16]

  • Institute: Indian Institute of Technology Madras
  • Thesis Title: Approximation and Parameterized Algorithms for Finding Hitting Sets
    • The thesis is on the approximability and parameterized complexity of finding hitting sets like odd cycle transversal, clique transversals and vertex cover in graphs using perfectness, linear programming and polyhedral combinatorics.
M.S. (by Research) [2010 - 12]
  • Institute: Indian Institute of Technology Madras
  • Thesis Title: r-Partization and Above Guarantee Vertex Cover
    • The thesis is on the study of the parameterized complexity of the r-Partization  problem of finding a minimum cardinality set of vertices whose deletion makes the graph r-colorable in perfect graphs and split graphs.

B. E Computer Science & Engineering [2003 - 07]

  • College/University: SSN College of Engineering, Anna University, Chennai
  • Project Title: Performance Tuning of Distributed Web Services
    • An integrated architecture to address the security and service discovery requirements of distributed applications was designed and the performance of the proposed architecture was compared with existing distributed environment paradigms like RMI, RMI-IIOP and CORBA.

Courses@IITM

MS Courses

Parameterized Algorithms; Advances in Complexity Theory; Parallel and Randomized Algorithms; Advanced Data Structures and Algorithms

Graph Theory; Cryptography; Mathematical Concepts of Computer Science; Formal Language Theory

Kernelization (at Institute of Mathematical Sciences, Chennai)

PhD Courses

Approximation Algorithms; Modern Techniques in Theory of Computation; Advanced Theory of Computation

Discrete Mathematics; Linear Algebra; Applied Linear Algebra; Mathematical Logic; Combinatorial Optimization

Infinite Discrete Structures (at Institute of Mathematical Sciences, Chennai)

Co-Academic 

Conference Activities

  • Member of the WALCOM 2014 Organizing Committee -  International Workshop on Algorithms and Computation, Feb 2014
  • Reviewed submissions to STACS 14, ESA 15, CALDAM 16, WG 17, COCOON 17, IPEC 17, FSTTCS 17 and CALDAM 18.

Workshop Talks

  • Lectured on Parameterized Algorithms at the ACM Summer School on Graph Theory and Graph Algorithms, IIT Gandhinagar, 2017
  • Lectured on NP-completeness Theory at the IARCS-ACM Workshop on Algorithms, IIIT Hyderabad, 2013
Teaching Assistant 
  • Mathematical Concepts for Computer Science (2010, 2014)
  • Advanced Data Structures & Algorithms (2011, 2012, 2013) 
    • Outstanding Teaching Assistant award (2011, 2012)
  • Advanced Complexity Theory (2012)
  • Approximation Algorithms (2013, 2015)
  • Modern Techniques in Theory of Computation (2014)