Paper by Erik D. Demaine

Reference:

Erik D. Demaine, David Eppstein, Adam Hesterberg, Kshitij Jain, Anna Lubiw, Ryuhei Uehara, and Yushi Uno, “Reconfiguring Undirected Paths”, in Proceedings of the 17th International Symposium on Algorithms and Data Structures (WADS 2019), August 5–7, 2019, pages 353–365.

Abstract:

We consider problems in which a simple path of fixed length, in an undirected graph, is to be shifted from a start position to a goal position by moves that add an edge to either end of the path and remove an edge from the other end. We show that this problem may be solved in linear time in trees, and is fixed-parameter tractable when parameterized either by the cyclomatic number of the input graph or by the length of the path. However, it is PSPACE-complete for paths of unbounded length in graphs of bounded bandwidth.

Comments:

This paper is available as arXiv:1905.00518 and from SpringerLink.

Length:

The paper is 13 pages.

Availability:

The paper is available in PDF (274k).

See information on file formats.

[Google Scholar search]