Kshitij Gajjar

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 $n \times n$ grid is labeled with an ordering constraint -- ascending (A) or descending (D) -- and the goal is to fill the grid with the numbers 1 through $n^2$ such that each row and column respects its constraint. We provide a complete characterization of solvable puzzles: a puzzle admits a solution if and only if its associated constraint graph is acyclic, which translates to a simple "at most one switch" condition on the A/D labels. When solutions exist, we show that their count is given by a hook length formula. For unsolvable puzzles, we present an $O(n)$ algorithm to compute the minimum number of label flips required to reach a solvable configuration. Finally, we consider a generalization where rows and columns may specify arbitrary permutations rather than simple orderings, and establish that finding minimal repairs in this setting is NP-complete by a reduction from feedback arc set.

Kshitij Gajjar, Agastya Vibhuti Jha, Manish Kumar et al.

Reconfiguring two shortest paths in a graph means modifying one shortest path to the other by changing one vertex at a time so that all the intermediate paths are also shortest paths. This problem has several natural applications, namely: (a) revamping road networks, (b) rerouting data packets in synchronous multiprocessing setting, (c) the shipping container stowage problem, and (d) the train marshalling problem. When modelled as graph problems, (a) is the most general case while (b), (c) and (d) are restrictions to different graph classes. We show that (a) is intractable, even for relaxed variants of the problem. For (b), (c) and (d), we present efficient algorithms to solve the respective problems. We also generalize the problem to when at most $k$ (for a fixed integer $k\geq 2$) contiguous vertices on a shortest path can be changed at a time.