6 papers
Permutation Match Puzzles: How Young Tanvi Learned About Computational Complexity
Kshitij Gajjar, Neeldhara Misra
We study a family of sorting match puzzles on grids, which we call permutation match puzzles. In this puzzle, each row and column of a grid is labeled with an ordering…
m-Eternal Domination and Variants on Some Classes of Finite and Infinite Graphs
Tiziana Calamoneri, Federico Corò, Neeldhara Misra +2
We study the m-Eternal Domination problem, which is the following two-player game between a defender and an attacker on a graph: initially, the defender positions k guards on verti…
On a Characterization of Spartan Graphs
Neeldhara Misra, Saraswati Girish Nanoti
The eternal vertex cover game is played between an attacker and a defender on an undirected graph . The defender identifies vertices to position guards on to begin with. The…
The Cost and Complexity of Minimizing Envy in House Allocation
Jayakrishnan Madathil, Neeldhara Misra, Aditi Sethia
We study almost-envy-freeness in house allocation, where houses are to be allocated among agents so that every agent receives exactly one house. An envy-free allocation nee…
On the Parameterized Complexity of Diverse SAT
Neeldhara Misra, Harshil Mittal, Ashutosh Rai
We study the Boolean Satisfiability problem (SAT) in the framework of diversity, where one asks for multiple solutions that are mutually far apart (i.e., sufficiently dissimilar fr…
Envy-Free and Efficient Allocations for Graphical Valuations
Neeldhara Misra, Aditi Sethia
We consider the complexity of finding envy-free allocations for the class of graphical valuations. Graphical valuations were introduced by Christodoulou et. al.(2023) as a structur…