Approximate Max kCut with Subgraph Guarantee

Abstract We study the following variant of the Max kCut problem Given an input graph G with positively weighted edges and k colors the number k being xed and not dependent on the input instance we wish to compute a subgraph H of G containing lots of heavy edges and a color assignment c V k such that a all edges in H are properly colored and b a large fraction of edges in G nH is properly colored We give several de nitions of lots and large fraction and give fast polynomial time algorithms to compute such color assignments This problem is related to the frequency allocation problems for cellular telephone networks but could be useful in other scenarios too Introduction In the frequency allocation problem for cellular telephones we are given a set of k frequencies henceforth referred to as colors and a weighted input graph which intuitively models a network of radio transmitters In the graph vertices correspond to transmitters and an edge u v denotes the fact that if u and v ge