Optimal Path Cover for Graphs of Small Treewidth

This paper studies the optimal path cover problem in graphs of small treewidth. Let G=(V, E) be a graph modeled by network with vertex set V and edge set E. Given a specified vertex set S_VsubeV(G), a path cover is a path P of G such that S_VsubeV(P). A path cover PC is optimal if the cost of PC is minimum. Optimal path cover problem is essential in the route design, especially, when the group broadcast is applied. Optimal path cover problem is NP-hard in general graphs. Since the graph representing the modern communication network has small treewidth, we restrict the problem in small treewidth graphs. Suppose the treewidth of G is k. We present an algorithm for the optimal path cover problem. Its time complexity isO(|V|2^k*k!) in the worst case.