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)G=(V,E) be a graph with a demand function b:V→Z+b:V→Z+ and a gateway  g∈V∖Vsg∈V∖Vs, where Vs={v∈V:b(v)>0}Vs={v∈V:b(v)>0} is the set of source nodes  . A flow ϕuϕu of a source node uu is a multiset of b(u)b(u) paths in GG from uu to gg. A flow ϕϕ on GG is a set with one flow for each source node. Every flow ϕϕ defines a multigraph GϕGϕ with vertex set VV and all edges in the paths in ϕϕ. A distance-  ddedge coloring   of a flow ϕϕ is an edge coloring of GϕGϕ such that two edges with the same color are at distance at least dd in GG. The distance-  ddflow coloring problem   (FCPdFCPd) is the problem of obtaining a flow ϕϕ on GG with a distance-dd edge coloring where the number of used colors is minimum. For any fixed d≥3d≥3, we prove that FCPdFCPd is NP-hard even on a bipartite graph with just one source node. For d=2d=2, we also prove NP-hardness on a bipartite graph with multiples sources. For d=1d=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(logn)O(logn) even on nn-vertex paths, for any d≥1d≥1.