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: For every fixed k >= 3, it is NP-Complete to decide whether src(G) <= k even when the graph G is bipartite. 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. [4] hardness for the even case. 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. For a directed graph G, it is NP-Complete to decide whether rc(G) <= 2. |
Year | DOI | Venue |
---|---|---|
2011 | 10.4230/LIPIcs.FSTTCS.2011.241 | Leibniz International Proceedings in Informatics |
Keywords | Field | DocType |
Computational Complexity,Rainbow Connectivity,Graph Theory,Fixed Parameter Tractable Algorithms | Discrete mathematics,Edge coloring,Graph toughness,Combinatorics,Bound graph,Graph power,Cycle graph,Connectivity,Mathematics,Complement graph,Path graph | Conference |
Volume | ISSN | Citations |
13 | 1868-8969 | 12 |
PageRank | References | Authors |
0.79 | 6 | 3 |
Name | Order | Citations | PageRank |
---|---|---|---|
Prabhanjan Ananth | 1 | 234 | 18.43 |
Meghana Nasre | 2 | 98 | 12.80 |
Kanthi K. Sarpatwar | 3 | 30 | 8.03 |