Abstract: The colored multiway cut problem generalizes the traditional multiway cut problem. It is motivated by data partitioning in Peer-to-Peer networks. Given a graph G with color dependent edge weights and a partial coloration on some distinguished vertices,the colored multiway cut problem is to extend the partial coloration such that all the vertices are colored and the total weight of edges that have different colored endpoints is minimized. A polynomial time exact algorithm was presented for almost trees with parameter k. That is to say, the colored multiway cut problem is fixed-parameter tractable with respect to the parameter k, which is defined as the maximum, over all biconnected components C of the graph G, of the number of edges that must be removed from C to obtain a tree.

Key words: Algorithms,Colored multiway cuts,Fixed-parameter tractable,Almost trees with parameter k