Research

My PhD thesis is on understanding more about the exact power operation on graphs. Given a graph $G$ and an integer $k$, the conventional graph power operation returns a graph $G^k$ with the same vertex set as $G$ and an edge between any two vertices that are at a distance at most $k$ in the input graph $G$.

The exact power operation $\text{ex}(G,k)$ is slightly more granular: instead of joining vertices which are at a distance at most $k$, the exact power operation only joins vertices which are at a distance exactly $k$ in the input graph.

For any such graph operation, a pertinent question becomes: can we "undo" it? That is, given a graph $H$, can we construct a graph $G$ such that, $H=\text{ex}(G,k)$ (for some fixed $k$)? This is the objective of the thesis project: we focus on designing efficient algorithms to answer exactly this question.