Research interest
Graph Theory and Algorithms
Funded projects
"Algorithmic study on hereditary graph properties", 9 Jan 2023 - 8 Jan 2026, MATRICS scheme, Science and Engineering Research Board, Govt. of India
"Complexity dichotomies for graph modification problems", 24 Dec 2019 - 23 Jun 2022, Startup Research Grant, Science and Engineering Research Board, Govt. of India
Publications
DBLP (list1, list2); arXiv (list1, list2)
[U25a] Erdős-Gyárfás conjecture on graphs without long induced paths. with Anand Shripad Hegde and P. Shashank. Unpublished [arxiv, code]
[J25b] Bounds and extremal graphs for monitoring edge-geodetic sets in graphs. with Florent Foucaud, Pierre-Marie Marcille, Zin Mar Myint, Sagnik Sen and S Taruni. Discrete Applied Mathematics [preliminary version: C24a]
[J25a] Algorithms for subgraph complementation to some classes of graphs. with Dhanyamol Antony and Sagartanu Pal. Information Processing Letters [published version,preliminary version: [C23a]]
[C24b] Switching Classes: Characterization and Computation. with Dhanyamol Antony, Yixin Cao, and Sagartanu Pal. 49th International Symposium on Mathematical Foundations of Computer Science, MFCS 2024 (published version, arxiv)
[J24a] Cutting a tree with Subgraph Complementation is hard, except for some small trees. with Dhanyamol Antony, Sagartanu Pal, and R. Subashini. Journal of Graph Theory (published version, preliminary version: [C22a])
[C24a] Monitoring edge-geodetic sets in graphs: extremal graphs, bounds, complexity. with Florent Foucaud, Pierre-Marie Marcille, Zin Mar Myint, Sagnik Sen and S Taruni. CALDAM 2024 [published version, arxiv(part 1)]
[C23b] Contracting edges to destroy a pattern: A complexity study. with Dipayan Chakraborty. FCT 2023 [arxiv]
[C23a] Algorithms for subgraph complementation to some classes of graphs. with Dhanyamol Antony and Sagartanu Pal. Eurocomb 2023 [arxiv,published version]
[J22d] On Deeply Critical Oriented Cliques. with Christopher Duffy, Pavan P D, and Sagnik Sen. Journal of Graph Theory (preliminary version: [C21b]) [published version, code]
[C22a] Cutting a tree with Subgraph Complementation is hard, except for some small trees. with Dhanyamol Antony, Sagartanu Pal, and R. Subashini. LATIN 2022. [arxiv]
[J22c] On subgraph complementation to H-free graphs. with Dhanyamol Antony, Jay Garchar, Sagartanu Pal, Sagnik Sen, and R. Subashini. Algorithmica (preliminary version: [C21a]) [arxiv, published version]
[J22b] Incompressibility of H-free edge modification problems: Towards a dichotomy. with Dániel Marx. Journal of Computer and System Sciences. doi:10.1016/j.jcss.2021.11.001(preliminary version: [C20a]) [arxiv; code; published version]
[J22a] A polynomial kernel for Diamond-free Editing. with Yixin Cao, Ashutosh Rai, and Junjie Ye. Algorithmica (preliminary version: [C18a]). doi:10.1007/s00453-021-00891-y [published version]
[C21b] On Deeply Critical Oriented Cliques. with Christopher Duffy, Pavan P D, and Sagnik Sen. EUROCOMB 2021. doi:10.1007/978-3-030-83823-2_101 [arxiv; published version]
[C21a] On subgraph complementation to H-free graphs. with Dhanyamol Antony, Jay Garchar, Sagartanu Pal, Sagnik Sen, and R. Subashini. WG 2021. doi:10.1007/978-3-030-86838-3_9 [arxiv; published version]
[C20a] Incompressibility of H-free edge modification problems: Towards a dichotomy. with Dániel Marx. ESA 2020. doi:10.4230/LIPIcs.ESA.2020.72. [arxiv; a talk by Dániel Marx; published version; code, invited to the special issue of JCSS]
[J20a] Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds. with Yixin Cao. Information and Computation. 2020 (preliminary version: [C17a]). doi:10.1016/j.ic.2020.104514 [published version]
[C18a] A polynomial kernel for Diamond-free Editing. with Yixin Cao, Ashutosh Rai, and Junjie Ye. 26th Annual European Symposium on Algorithms (ESA 2018): 10:1 - 10:13. doi:10.4230/LIPIcs.ESA.2018.10 [arxiv] [published version] [a talk by Yixin Cao in Worker 2019]
[J17b] Dichotomy results on the hardness of H-free edge modification problems. with N. R. Aravind and Naveen Sivadasan. SIAM Journal on Discrete Mathematics. 31(1): 542-561 (2017) (preliminary versions: [C15b] and [C16b]). doi: 10.1137/16M1055797. [published version]
[C17a] Minimum Fill-In: Inapproximability and Almost Tight Lower Bounds. with Yixin Cao. ACM-SIAM Symposium on Discrete Algorithms (SODA 2017): 875--880. doi:10.1137/1.9781611974782.55. [published version, slides]
[J17a] On polynomial kernelization of ℋ-free Edge Deletion. with N. R. Aravind and Naveen Sivadasan. Algorithmica 79(3): 654-666 (2017) . doi:10.1007/s00453-016-0215-y (preliminary version: [C14a]) [published version]
[C16b] Parameterized lower bounds and dichotomy results for the NP-completeness of H-free edge modification problems. with N. R. Aravind and Naveen Sivadasan. In LATIN, 2016:82--95. doi:10.1007/978-3-662-49529-2_7 [published version]
[C16a] Compressing bounded degree graphs. with Pål Grønås Drange and Markus Sortland Dregi. In LATIN 2016, 2016:362--375. doi:10.1007/978-3-662-49529-2_27 [published version]
[J15a] The chromatic discrepancy of graphs. with N. R. Aravind. Subrahmanyam Kalyanasundaram and Naveen Sivadasan. Discrete Applied Mathematics 184: 40-49 (2015). doi:10.1016/j.dam.2014.10.038 [published version]
[C15b] Parameterized Lower Bound and NP-Completeness of Some H-Free Edge Deletion Problems. with N. R. Aravind and Naveen Sivadasan. COCOA 2015: 424-438. doi:10.1007/978-3-319-26626-8_31
[C15a] Parameterized Lower Bound and Improved Kernel for Diamond-free Edge Deletion. with Naveen Sivadasan. IPEC 2015: 365-376. doi:10.4230/LIPIcs.IPEC.2015.365
[C14a] On polynomial kernelization of ℋ-free Edge Deletion. with N. R. Aravind and Naveen Sivadasan. IPEC 2014: 28-38. doi:10.1007/978-3-319-13524-3_3
[J11a] Perfectly colorable graphs. R. B. Sandeep. Information Processing Letters. 111(19): 960-961 (2011). doi:10.1016/j.ipl.2011.07.001 [arxiv, published version]