Computational Complexity of Robot Arm Simulation Problems

摘要

We consider a simulation problem of a general mechanism by a robot arm. A robot arm can be modeled by a path P, and the target is modeled by a general graph G. Then the problem asks if there is an edge-weighted Eulerian path of G spanned by P. We first show that it is strongly NP-hard even if edge lengths are restricted. Then we consider two different variants of this problem. We first allow the edges in P to be elastic, and minimize the elastic ratio when G is a path. Second, we allow P to cover an edge of G twice or more. The problem is weakly NP-hard even if G is an edge. We thus assume that each edge of G is covered by P exactly twice, and obtain three hardness results and one polynomial-time algorithm when G and edge lengths are restricted.