License: Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported license (CC BY-NC-ND 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.FSTTCS.2011.241
URN: urn:nbn:de:0030-drops-33535
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2011/3353/
Go to the corresponding LIPIcs Volume Portal

Ananth, Prabhanjan ; Nasre, Meghana ; Sarpatwar, Kanthi K.

Rainbow Connectivity: Hardness and Tractability

pdf-format:
35.pdf (0.4 MB)

Abstract

A path in an edge colored graph is said to be a rainbow path if no two edges on the path have the same color. An edge colored graph is (strongly) rainbow connected if there exists a (geodesic) rainbow path between every pair of vertices. The (strong) rainbow connectivity of a graph G, denoted by (src(G), respectively)
rc(G) is the smallest number of colors required to edge color the graph such that G is (strongly) rainbow connected. In this paper we study the rainbow connectivity problem and the strong rainbow connectivity problem from a computational point of view. Our main results can be summarised as below:
1) For every fixed k >= 3, it is NP-Complete to decide whether src(G) <= k even when the graph G is bipartite.
2) For every fixed odd k >= 3, it is NP-Complete to decide whether rc(G) <= k. This resolves one of the open problems posed by Chakraborty et al. (J. Comb. Opt., 2011) where they prove the hardness for the even case.
3) The following problem is fixed parameter tractable: Given a graph G, determine the maximum number of pairs of vertices that can be rainbow connected using two colors.
4) For a directed graph G, it is NP-Complete to decide whether rc(G) <= 2.

BibTeX - Entry

@InProceedings{ananth_et_al:LIPIcs:2011:3353,
  author =	{Prabhanjan Ananth and Meghana Nasre and Kanthi K. Sarpatwar},
  title =	{{Rainbow Connectivity: Hardness and Tractability}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{241--251},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Supratik Chakraborty and Amit Kumar},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2011/3353},
  URN =		{urn:nbn:de:0030-drops-33535},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.241},
  annote =	{Keywords: Computational Complexity, Rainbow Connectivity, Graph Theory, Fixed Parameter Tractable Algorithms}
}

Keywords: Computational Complexity, Rainbow Connectivity, Graph Theory, Fixed Parameter Tractable Algorithms
Collection: IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)
Issue Date: 2011
Date of publication: 01.12.2011

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI