Abhiruk Lahiri

Abhiruk Lahiri

Research and Teaching Assistant at Heinrich Heine University

Posts by Collection

portfolio

Photography

I still take photographs but in an unorganised fashion. I hope in the distant future I will have a nicer photography page. Until then, enjoy my Instagram page. Thanks for stopping by.

publications

Maximum independent set on B1-VPG graphs

Published in Proceedings of International Conference on Combinatorial Optimization and Applications, 2015

We present two approximation algorithms for the maximum independent set problem over the class of B1-VPG graphs. We also showed NP-completeness of the decision version restricted to unit length equilateral B1-VPG graphs.

Download here

Improved approximation for maximum edge colouring problem

Published in Discrete Applied Mathematics, 2021

We show an 8/5 algorithm for the maximum edge 2-colouring problem when the underlying graph is triangle-free and has a perfect matching. We also show that this algorithm cannot achieve an approximation ratio better than 58/37 on a triangle-free graph that has a perfect matching.

Download here

On chromatic number of (n, m)-graphs

Published in Proceedings of European Conference on Combinatorics, Graph Theory and Applications, EuroComb, 2021

We study this chromatic number for the family of sparse graphs, partial 2-trees, graphs with bounded maximum degree and degeneracy.

Download here

Parameterized convexity testing

Published in Proceedings of 5th Symposium on Simplicity in Algorithms, SOSA, 2022

We show that the number of distinct discrete derivatives, as opposed to the input size, is a better input parameter to express the complexity of convexity testing. We present a nonadaptive convexity tester with query complexity O(log s/epsilon) and complement it with a nearly matching lower bound.

Download here

Reconfiguring shortest paths in graphs

Published in Proceedings of 36th AAAI Conference on Artificial Intelligence, AAAI, 2022

We show that shortest path reconfiguration problem is intractable, even for relaxed variants. We present efficient algorithms for a few restricted variants. We also generalize the problem to when at most k (for a fixed integer k greater than 2) contiguous vertices on a shortest path can be changed at a time.

Download here

On comparable box dimension

Published in Proceedings of 38th International Symposium on Computational Geometry, SoCG, 2022

We show that proper minor-closed classes have bounded comparable box dimensions and explore further properties of this notion.

Download here

Rainbow trees in uniformly edge-colored graphs

Published in Random Structures and Algorithms, 2022

We obtain sufficient conditions for the emergence of spanning and almost-spanning bounded-degree rainbow trees in various host graphs, having their edges colored independently and uniformly at random, using a predetermined palette.

Download here

Geometric dominating set and set cover via local search

Published in Computational Geometry: Theory and Applications (to appear), 2023

We present two principal results, both involving local-search PTASs for geometric covering problems. The first is an approximation to the minimum-sized dominating set for a set of convex homothets, and the second is an approximation to the minimum-sized set cover, where the sets are based on convex pseudodisks.

Download here

How does fairness affect the complexity of gerrymandering?

Published in Proceedings of 22nd International Conference on Autonomous Agents and Multiagent Systems (to appear), 2023

We studied variants of the problem with some additional restrictions on solutions, that place limits on the efficacy of possible gerrymandering strategies.

talks

teaching