Visualizing Baranyai’s theorem for the case when n=2.

# Neeldhara Misra

Smt. Amba and Sri. V S Sastry Chair Associate Professor

Computer Science and Engineering at IIT Gandhinagar

(she/her)

Blog ⸱ Mastodon ⸱ DBLP ⸱ Contact

My broad research interests include — in no particular order: algorithm design, computational social choice, combinatorial games. You can find out more about my work here.

Recent PCs: FUN 2022, MFCS 2022, IPEC 2022, Compute 2022, CALDAM 2023, IPEC 2023 (co-chair with Magnus Wahlström)

## Latest News

My course on *Getting Started with Competitive Programming* will run from 23 Jan 2023 to 14 Apr 2023. The deadline to register is **30th January 2023**. While I will not be an instructor for the upcoming run, I hope you have a chance to check it out if it is of interest to you!

(More generally, the NPTEL Jan 2023 semester is open with courses across engineering, humanities and social sciences. You can enrol in these courses at no cost here and get a certification by taking up a proctored exam for a nominal fee of Rs 1,000 per course.)

Joint work with Manas Mulpuri, Prafullkumar Tale, and Gaurav Viramgami ⸱ To Appear at FSTTCS 2022 ⸱ Preprint available from ArXiV

The game of rendezvous with adversaries is a game on a graph played by two players: Facilitator and Divider. Facilitator has two agents and Divider has a team of k agents. While the initial positions of Facilitator’s agents are fixed, Divider gets to select the initial positions of his agents. Then, they take turns to move their agents to adjacent vertices (or stay put) with Facilitator’s goal to bring both her agents at same vertex and Divider’s goal to prevent it. The computational question of interest is to determine if Facilitator has a winning strategy against Divider with k agents. In this work, we prove that this problem is hard even when the graph is very close to a forest.

Joint work with Harshil Mittal and Sarasati Nanoti ⸱ To Appear at CCCG 2022

A perfect matching M on a set P of n points is a collection of line segments with endpoints from P such that every point belongs to exactly one segment. A matching is non-crossing if the line segments do not cross. We introduce a notion of distance between non-crossing matchings, and investigate the complexity of the problem of finding matchings that are far apart with respect to this notion of distance.

Joint work with N. R. Aravind and Harshil Mittal ⸱ To appear at FUN 2022 ⸱ Preprint available from ArXiV

We introduce a generalization of “Solo Chess”, a single-player variant of the game that can be played on chess.com. We show that this version of the game is NP-complete even if played only by rooks with at most two captures left, or only by queens with exactly two captures left. On the other hand, solvable instances of rooks on 1D boards and pawns on 2D boards can efficiently characterized. Find out more on Twitter or at the blog.

Joint work with Saraswati Nanoti ⸱ To appear at CSR 2022 ⸱ Preprint available from ArXiV

Eternal Vertex Cover is a dynamic variant of the vertex cover problem. The complexity of the problem on bipartite graphs is open, as is the question of whether the problem admits a polynomial kernel. We settle both these questions by showing that Eternal Vertex Cover is NP-hard and does not admit a polynomial compression even on bipartite graphs of diameter six. We also show that the problem admits a polynomial time algorithm on the class of cobipartite graphs.

Joint work with Harshil Mittal ⸱ Published in Theoretical Computer Science (Dec 2021) ⸱ A shorter version was accepted at COCOON 2020 ⸱ Preprint available from ArXiV

Imbalance is a layout optimization problem, where we would like to order the vertices of a graph so that, roughly speaking, vertices have their neighbors split up as equally as possible on their left and right. We examine the parameterized complexity of the problem with respect to a structural parameter called twin cover.

No matching items

*All News*

#### In case you care for (sporadic) updates by email.

I mostly plan to write some notes to self: I can’t imagine that you’d be interested, but if, for some reason, you are, you are welcome.