This is also related to patch theory [2, 3, 4, 5, 6], a theory that seeks mathematise version control systems like, and to provide provably correct merging algorithms. Patch theory arose in the context of the DARCS system. [7] connects patch theory with homotopy type theory.
[1] https://ifl2014.github.io/submissions/ifl2014_submission_32....
[2] J. Dagit, Type-Correct Changes - A Safe Approach to Version Control Implementation.
[3] G. Sittampalam, Some properties of darcs patch theory.
[4] I. Lynagh, Camp Patch Theory.
[5] D. Roundy, Implementing the darcs patch formalism ... and verifying it.
[6] J. Jacobson, A Formalization Of Darcs Patch Theory Using Inverse Semigroups.
[7] C. Angiuli, E. Morehouse, D. R. Licata, R. Harper, Homotopical Patch Theory.
About our use case: We developed an algorithm for creating "semantic diffs" between two source code trees. Starting from a graphical (AST) representation of the source code of an entire software project, such a diff would basically tell you how you can transform one tree into the other using a range of edit operations (e.g. insert, delete, copy, paste, modify). The advantage compared to line-by-line diffs is that the latter work only on the text-level (i.e. "this line has been removed, this other line has been added"), whereas the former can actually tell you what changed on a semantic level (i.e. "this argument was inserted into this function and this variable name was changed").
For big projects, this is quite a computational challenge and can (could) only be solved using approximations and shortcuts. Having a polynomial-time algorithm for this would therefore be a huge deal.
I hope that the proof will soon lead to practical implementations of the algorithm.