Improved approximation for maximum edge colouring problem

Abstract

The anti-Ramsey number, ar(G,H) is the minimum integer k such that in any edge colouring of G with k colours there is a rainbow subgraph isomorphic to H, namely, a copy of H with each of its edges assigned a different colour. The notion was introduced by Erdös and Simonovits in 1973. Since then the parameter has been studied extensively. The case when H is a star graph was considered by several graph theorists from the combinatorial point of view. Recently this case received the attention of researchers from the algorithm community because of its applications in interface modelling of wireless networks. To the algorithm community, the problem is known as maximum edge q-colouring problem: Find a colouring of the edges of G, maximizing the number of colours satisfying the constraint that each vertex spans at most q colours on its incident edges. It is easy to see that the maximum value of the above optimization problem equals ar(G,K1,q+1)−1. In this paper, we study the maximum edge 2-colouring problem from the approximation algorithm point of view. The case q=2 is particularly interesting due to its application in real-life problems. Algorithmically, this problem is known to be NP-hard for q≥2. For the case of q=2, it is also known that no polynomial-time algorithm can approximate to a factor less than 3/2 assuming the unique games conjecture. Feng et al. showed a 2-approximation algorithm for this problem. Later Adamaszek and Popa presented a 5/3-approximation algorithm with the additional assumption that the input graph has a perfect matching. Note that the obvious but the only known algorithm issues different colours to the edges of a maximum matching (say M) and different colours to the connected components of G∖M. In this article, we give a new analysis of the aforementioned algorithm to show that for triangle-free graphs with perfect matching the approximation ratio is 8/5. We also show that this algorithm cannot achieve a factor better than 58/37 on triangle free graphs that has a perfect matching. The contribution of the paper is a completely new, deeper and closer analysis of how the optimum achieves a higher number of colours than the matching based algorithm, mentioned above.