Note: The following list is not updated frequently, please consult my DBLP or google scholar for a more up-to-date list.
Survey
Sushmita Gupta, Sanjukta Roy, Saket Saurabh, and Meirav Zehavi. Some Hard Stable Marriage Problems: A Survey on Multivariate Analysis
Invited to monograph Mathematical Programming and Game Theory, Springer, 141--157, 2018. Available online at https://link.springer.com/chapter/10.1007/978-981-13-3059-9_8
Published Articles
Sushmita Gupta, Pallavi Jain, Aditya Petety, and Sagar Singh. Parameterized complexity of d-hitting set with Quotas
Accepted to 47th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM), 2021.
Sushmita Gupta, Pallavi Jain, Sanjukta Roy, Saket Saurabh, and Meirav Zehavi. On the (Parameterized) Complexity of Almost Stable Marriage
Accepted to IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), 2020.
Sushmita Gupta, Pallavi Jain, and Saket Saurabh. Well-Structured Committees
In the proc. of the 29th International Joint Conference on Artificial Intelligence (IJCAI), 2020.
Edith Elkind, Piotr Faliszewski, Sushmita Gupta, and Sanjukta Roy. Algorithms for Evaluating Candidate Success in Structured Elections
Accepted for the 19th International Conference on Autonomous Agents and MultiAgent Systems (AAMAS), 2020, pp 366--374. Link here.
Sushmita Gupta, Pallavi Jain, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Gehrlein Stability in Committee Selection: Parameterized Hardness and Algorithms
In the Journal of Autonomous Agents and Multi-Agent Systems (JAAMAS) 34(27):1--21, 2020. Online at https://doi.org/10.1007/s10458-020-09452-z
A preliminary version appeared in the proc. of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2019, 511-519.
Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Quadratic Vertex Kernel for Rainbow Matching
Algorithmica, 82:881--897, 2020. Available online at https://doi.org/10.1007/s00453-019-00618-0
A preliminary version of this paper appeared in the proc. of the International Symposium on Mathematical Foundations of Computer Science (MFCS), 71:1--71:1, 2017. https://doi.org/10.4230/LIPIcs.MFCS.2017.71
Sushmita Gupta, Pranabendu Misra, Saket Saurabh and Meirav Zehavi. Popular Matching in Roommates Setting is NP-hard.
ACM Transactions on Computation Theory, Volume 13, Issue 2, 1--20. Available online here
In the proc. of the 30th Annual (ACM-SIAM) Symposium on Discrete Algorithms (SODA), 2019, 2810--2822. Available online at https://arxiv.org/abs/1803.09370
Invited as a ``Technical Contribution'' to the Bulletin of European Association of Computer Science (BEATCS), editor-in-chief Prof. Kazuo Iwama. Available online at http://bulletin.eatcs.org/index.php/beatcs/issue/view/32
Sushmita Gupta, Saket Saurabh, Ramanujan Sridharan, and Meirav Zehavi. On Succinct Encodings for the Tournament Fixing Problem
In the proc. of the Twenty-Eighth International Joint Conference on Artificial Intelligence (IJCAI), 2019: 322--328.
Sushmita Gupta, Sanjukta Roy, Saket Saurabh, Meirav Zehavi. Parameterized Algorithms and Kernels for Rainbow Matching
Algorithmica 81(4): 1684-1698 (2019).
Sushmita Gupta, Sanjukta Roy, Saket Saurabh, Meirav Zehavi. Balanced Stable Marriage: How Close Is Close Enough?
Theoretical Computer Science, available online here
In the proc. of the Algorithms and Data Structures - 16th International Symposium (WADS), 2019, 423-437.
Akanksha Agrawal, Sushmita Gupta, Pallavi Jain, R. Krithika. Quadratic Vertex Kernel for Split Vertex Deletion.
In the proc. of the 11th International Conference on Algorithms and Complexity (CIAC), 2019: 1--12.
Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. When Rigging a Tournament, Let Greediness Blind You.
In the proc. of the 27th International Joint Conference on Artificial Intelligence (IJCAI), 2018. Available online at https://doi.org/10.24963/ijcai.2018/39
Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Winning a Tournament by Any Means Necessary.
In the proc. of the 27th International Joint Conference on Artificial Intelligence (IJCAI), 2018. Available online at https://doi.org/10.24963/ijcai.2018/38
Sushmita Gupta, Fahad Panolan, Saket Saurabh and Meirav Zehavi. Stability in Barter Exchange Markets.
In the Journal of Autonomous Agents and Multi-Agent Systems (JAAMAS) 33(5): 518-539 (2019). Link
A preliminary version appeared in the proc. of the International Conference on Autonomous Agents and Multiagent Systems (AAMAS), 2018.
Sushmita Gupta, Sanjukta Roy. Stable Matching Games: Manipulation via Subgraph Isomorphism.
Algorithmica, 80(9):2551--2573 available online https://doi.org/10.1007/s00453-017-0382-5
Preliminary version appeared in the proc. of the 36th (IARCS) Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Springer LNCS, 65 29:1--29:14, 2016. https://doi.org/10.4230/LIPIcs.FSTTCS.2016.29
Deeksha Adil, Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Parameterized Algorithms for the Stable Matching Problem with Ties and Incomplete Lists.
Theoretical Computer Science, 723:1-10, 2018.
Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Parameterized Algorithms and Kernels for Rainbow Matching.
Accepted to Algorithmica. Available on request.
Preliminary version appeared in the proc. of the International Symposium on Mathematical Foundations of Computer Science (MFCS), 71:1--71:13, 2017. https://doi.org/10.4230/LIPIcs.MFCS.2017.71
Sushmita Gupta, Sanjukta Roy, Saket Saurabh and Meirav Zehavi. Parameterized Analysis for Graph Group Activity Selection Problem
In the proc. of the International Symposium on Algorithmic Game Theory (SAGT), Springer LNCS, 106--118, 2017. https://doi.org/10.1007/978-3-319-66700-3_9
Sushmita Gupta, Kazuo Iwama and Shuichi Miyazaki. Total Stability in Stable Matching Games.
In the proc. of the 15th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT), 23:1--12. https://doi.org/10.4230/LIPIcs.SWAT.2016.23
Sushmita Gupta, Shahin Kamali and Alejandro Lopez-Ortiz. On the Advice Complexity of the k-Server Problem under Sparse Metrics.
Theory of Computing Systems, 59(3): 476--499, 2016. https://doi.org/10.1007/s00224-015-9649-x
Preliminary version appeared in the proc. of the International Colloquium on Structural Information and Communication Complexity, (SIROCCO), LNCS, 8179: 55--67. https://doi.org/10.1007/978-3-319-03578-9_5
Akanksha Agrawal, Sushmita Gupta, Saket Saurabh and Roohani Sharma. Improved Algorithms for Independent Feedback Vertex Set.
In the proc. of the 11th International Symposium on Parameterized and Exact Computation (IPEC), 2:1--2:14, 2016. https://doi.org/10.4230/LIPIcs.IPEC.2016.2
Joan Boyar, Sushmita Gupta and Kim Skak Larsen. Relative Interval Analysis of Paging Algorithms on Access Graphs.
Theoretical Computer Science 2015, 568:28--48, 2015. https://doi.org/10.1016/j.tcs.2014.11.035
Preliminary version appeared in the proc. of the Algorithms and Data Structures Symposium, (formerly Workshop on Algorithms and Data Structures), (WADS), LNCS 8037:195--206, 2013. https://doi.org/10.1007/978-3-642-40104-6_17
Sushmita Gupta, Venkatesh Raman and Saket Saurabh. Maximum r-Regular Induced Subgraph Problem: Fast Exponential Algorithms and Combinatorial Bounds.
SIAM Journal of Discrete Mathematics, 26(4):1758--1780, 2012. https://doi.org/10.1137/09077850X
A preliminary version of this paper, titled "Fast Exponential Algorithms for Maximum r-Regular Induced Subgraph Problems", appeared in the proc. of the Foundations of Software Technology and Theoretical Computer Science (FSTTCS), Springer LNCS, 4337:139--151, 2006.
Joan Boyar, Sushmita Gupta and Kim Skak Larsen. Access Graph Results for LRU versus FIFO under Relative Worst Order Analysis.
In the proc. of the Scandinavian Symposium and Workshops on Algorithm Theory, (SWAT), LNCS 7357:328--339, 2012. https://doi.org/10.1007/978-3-642-31155-0_29
Sushmita Gupta. Feedback Arc Set Problem in Bipartite Tournament.
Information Processing Letters (IPL) 105(4):150-154, 2008. https://doi.org/10.1016/j.ipl.2007.08.023
A preliminary version of this paper appeared in the proc. of the Conference on Theory and Applications of Models of Computation (TAMC), Springer LNCS 4484: 354--361, 2007