On the complexity of the flow coloring problem

Motivated by bandwidth allocation under interference constraints in radio networks, we define and investigate an optimization problem that combines the classical flow and edge coloring problems in graphs. Let G = ( V , E ) be a graph with a demand function b : V ? Z + and a gateway g ? V ? V s , where V s = { v ? V : b ( v ) 0 } is the set of source nodes. A flow ? u of a source node u is a multiset of b ( u ) paths in G from u to g . A flow ? on G is a set with one flow for each source node. Every flow ? defines a multigraph G ? with vertex set V and all edges in the paths in ? . A distance- d edge coloring of a flow ? is an edge coloring of G ? such that two edges with the same color are at distance at least d in G . The distance- d flow coloring problem ( F C P d ) is the problem of obtaining a flow ? on G with a distance- d edge coloring where the number of used colors is minimum. For any fixed d ? 3 , we prove that F C P d is NP-hard even on a bipartite graph with just one source node. For d = 2 , we also prove NP-hardness on a bipartite graph with multiples sources. For d = 1 , we show that the problem is polynomial in 3-connected graphs and bipartite graphs. Finally, we show that a list version of the problem is inapproximable in polynomial time by a factor of O ( log n ) even on n -vertex paths, for any d ? 1 .