Playing with model trains and calling it graph theory

My newest preprint, “Reconfiguring Undirected Paths” (with Demaine, Hesterberg, Jain, Lubiw, Uehara, and Uno, arXiv:1905.00518, considers an abstract model for such problems, in which the train track is modeled as an undirected graph and the train is a simple path in the graph. Here’s an example of an NCL problem transformed by our reduction into a path-sliding problem:

Our main results are a fixed-parameter tractable algorithm parameterized by train length (so it’s fast for short trains) and a linear time algorithm when the graph is a tree. For the parameterized version, if the graph has a path twice as long as the train that can be reached from the starting position of the train, and another long path that can reach the ending position, then we can maneuver the train onto the first long path, send it on an express route directly from the first long path to the second one, and then maneuver it from there into its final position.

Source: 11011110.github.io