Searching Optimal Cycle Cover for Graphs of Small Treewidth

In this paper, we propose an algorithm to search the optimal cycle cover 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 SVsubeV(G), a cycle cover is a cycle C of G such that every vertex in SV lies in cycle C. A cycle cover is called optimal if its cost is minimum. Cycle cover problem plays an important role in the construction of logic sub-network, especially, when the topology of the network is a cycle. It is shown that optimal cycle cover problem is NP-hard in general graphs. But the problem can be solved effectively when it is restricted to the graphs with small treewidth. Since the graph representing the modern communication network has small treewidth, our work is applicable in the real world. Suppose the treewidth of graph G is k. We present an algorithm for the optimal cycle cover problem. Its time complexity is O(|V|ldr2^kldrk!) in the worst case.