The main goal of this project is to provide structural analysis of two topics under the combinatorial reconfiguration framework. The first topic is on the k-Opt heuristic, a local search algorithm for the well known Travelling Salesman Problem, while the second topic is the Gray coding problem derived from one of the fundamental tasks in computer science, combinatorial generation. In light of recent results in 2024 that show hardness of computability for both topics, we propose to perform structurally-driven fine-grained analysis on them. On the one hand, such analysis can exploit the structural properties of relevant inputs to design efficient algorithms. On the other hand, it can tighten the established lower bounds on even more restricted instances. As a whole, this analysis can provide a better understanding of boundary of intractability for these two topics.