Path coloring

In graph theory, path coloring is a type of graph coloring where colors (or wavelengths ) are assigned to a set of paths in a graph such that any two paths sharing an edge receive different colors. The objective is typically to minimize the number of colors used. Path coloring is motivated by the problem of allocating optical bandwidth to communication requests in all-optical networks that utilize Wavelength-division multiplexing (WDM). ^[1]

Definitions

Path coloring may refer to either the WA problem or the RWA problem.

In the wavelength assignment problem (or WA problem), the input consists of a graph ${\displaystyle G}$ and a (multi)set of paths ${\displaystyle P}$ already defined on ${\displaystyle G}$. The task is to assign colors to the paths in ${\displaystyle P}$ such that any two paths sharing an edge in ${\displaystyle G}$ receive different colors. ^[2]

This formulation is equivalent to vertex coloring the conflict graph of ${\displaystyle P}$, which has one vertex for each path in ${\displaystyle P}$ and an edge between two vertices whenever the corresponding paths share an edge in ${\displaystyle G}$. ^[1]

In the routing and wavelength assignment problem (also wavelength routing problem or RWA problem), the input consists of a graph ${\displaystyle G}$ and a set of requests${\displaystyle R}$, where each request is a pair of nodes to be connected. For each request, the algorithm must both select a path connecting the two endpoints and assign a color to that path, such that paths sharing an edge receive different colors. ^[2]

The RWA problem thus decomposes into two subproblems: the routing problem of selecting a path for each request, and the WA problem of coloring the resulting paths. ^[1]

In general graphs where multiple paths exist between node pairs, these subproblems interact, making RWA more complex than WA alone.

Trees

In tree networks, the path connecting any two nodes is unique. Therefore, the routing subproblem becomes trivial, and wavelength routing in trees reduces to the WA problem. ^[1] For this reason, research on path coloring often focuses on tree topologies.

The load of an edge is defined as the number of paths passing through it, and the load of a set of paths ${\displaystyle L}$ is the maximum load over all edges. The load provides a lower bound on the number of colors required. ^[1]

Undirected and bidirected variants

Path coloring can be studied in both undirected and bidirected (directed) settings: ^[2]

• In undirected path coloring, the graph ${\displaystyle G}$ is undirected, and paths are undirected. Two paths conflict if they share any edge.
• In directed path coloring, the graph is bidirected (each undirected edge is replaced by two directed edges in opposite directions), and paths are directed. Two directed paths conflict only if they share a directed edge in the same direction.

The directed variant models networks where each physical fiber link has separate capacity for each transmission direction.

Complexity

Path coloring is NP-hard for both undirected and bidirected ring networks. For trees: ^{[1] [2]}

• Undirected path coloring in stars is equivalent to edge coloring of multigraphs and is therefore NP-hard.
• Directed path coloring is NP-hard even for binary bidirected trees.
• Path coloring can be solved optimally in polynomial time for trees of bounded degree or when the number of paths touching any node is ${\displaystyle O((\log n)^{1-\varepsilon })}$ for some ${\displaystyle \varepsilon >0}$.

Approximation algorithms

For undirected trees, a greedy algorithm using edge coloring of multigraphs achieves an approximation ratio of 3/2, which is tight. ^[1] An algorithm with absolute approximation ratio 4/3 and asymptotic approximation ratio 1.1 also exists. ^[2]

For bidirected trees, deterministic greedy algorithms achieve a ${\displaystyle 5L/3}$ upper bound on colors for paths of load ${\displaystyle L}$. Randomized algorithms improve this to ${\displaystyle 7L/5+o(L)}$ colors for binary bidirected trees. ^[1]

Relationship to call scheduling

Path coloring is closely related to call scheduling, which generalizes the problem by introducing bandwidth requirements and call durations. When all bandwidth requirements, edge capacities, and call durations equal 1, call scheduling reduces to the RWA problem, with colors corresponding to time slots. ^[2]

References

1. Caragiannis, Ioannis; Kaklamanis, Christos; Persiano, Giuseppe (2006), "Approximation Algorithms for Path Coloring in Trees", Efficient Approximation and Online Algorithms (PDF), Lecture Notes in Computer Science, vol. 3484, Berlin, Heidelberg: Springer, pp. 74–96, doi:10.1007/11671541_3, ISBN   978-3-540-32213-9
2. Erlebach, Thomas; Jansen, Klaus (2001), "The complexity of path coloring and call scheduling", Theoretical Computer Science , 255 (1–2): 33–50, doi:10.1016/S0304-3975(99)00152-8

External links

• A compendium of NP optimization problems by Viggo Kann (problem: Minimum Path Coloring)