Chandran, L. Sunil ;
Rajendraprasad, Deepak
Inapproximability of Rainbow Colouring
Abstract
A rainbow colouring of a connected graph G is a colouring of the edges of G such that every pair of vertices in G is connected by at least one path in which no two edges are coloured the same. The minimum number of colours required to rainbow colour G is called its rainbow connection number. Chakraborty, Fischer, Matsliah and Yuster have shown that it is NPhard to compute the rainbow connection number of graphs [J. Comb. Optim., 2011]. Basavaraju, Chandran, Rajendraprasad and Ramaswamy have reported an (r+3)factor approximation algorithm to rainbow colour any graph of radius r [Graphs and Combinatorics, 2012]. In this article, we use a result of Guruswami, Håstad and Sudan on the NPhardness of colouring a 2colourable 4uniform hypergraph using constantly many
colours [SIAM J. Comput., 2002] to show that for every positive integer k, it is NPhard to distinguish between graphs with rainbow connection number 2k+2 and 4k+2. This, in turn, implies that there cannot exist a polynomial time algorithm to rainbow colour graphs with less than twice the optimum number of colours, unless P=NP.
The authors have earlier shown that the rainbow connection number problem remains NPhard even when restricted to the class of chordal graphs, though in this case a 4factor approximation algorithm is available [COCOON, 2012]. In this article, we improve upon the 4factor approximation algorithm to design a lineartime algorithm that can rainbow colour a chordal graph G using at most 3/2 times the minimum number of colours if G is bridgeless and at most 5/2 times the minimum number of colours otherwise. Finally we show that the rainbow connection number of bridgeless chordal graphs cannot be polynomialtime approximated to a factor less than 5/4, unless P=NP.
BibTeX  Entry
@InProceedings{chandran_et_al:LIPIcs:2013:4368,
author = {L. Sunil Chandran and Deepak Rajendraprasad},
title = {{Inapproximability of Rainbow Colouring}},
booktitle = {IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
pages = {153162},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783939897644},
ISSN = {18688969},
year = {2013},
volume = {24},
editor = {Anil Seth and Nisheeth K. Vishnoi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2013/4368},
URN = {urn:nbn:de:0030drops43689},
doi = {10.4230/LIPIcs.FSTTCS.2013.153},
annote = {Keywords: rainbow connectivity, rainbow colouring, approximation hardness}
}
10.12.2013
Keywords: 

rainbow connectivity, rainbow colouring, approximation hardness 
Seminar: 

IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

Issue date: 

2013 
Date of publication: 

10.12.2013 