Polynomial-time algorithms for path movement problems on trees and unicyclic graphs

Abstract

© 2019 Taiwan Academic Network Management Committee. All rights reserved. In the path movement problem, we are given an undirected graph G = (V, E), a source vertex s, a destination vertex t, and a set of movable objects, called pebbles, which are placed on a subset of the vertices of a graph. We want to move a subset of the pebbles along the edges to a subset of the vertices of the graph such that there exists a path from s to t in graph G in such a way that all the vertices in that path are occupied by at least one pebble. The PathMax and the PathSum problems are the path movement problems in which we want to minimize the maximum movements and the total movements made by the pebbles, respectively. In [7], the researchers proved that both the problems are NP-hard in general graphs. In this paper, the PathMax and the PathSum problems are considered on special classes of graph G, that is, G is a tree and a unicyclic graph. More precisely, this paper shows that PathMax and PathSum problems can be easily solved in polynomial time when the input graph is a tree or a unicyclic graph.