<p>Edit: In the end I did find a reference for the reduction I remembered. It is given in <a href="http://www.cs.haifa.ac.il/~marinal/Networks.pdf" rel="nofollow">Edge intersection graphs of single bend paths on a grid</a> by Golumbic, Lipshteyn, and Stern. So, to sum up, the class of graphs obtained as intersections of paths on a grid contains all graphs. Therefore, path coloring on grids is as hard to approximate as graph coloring ($n^{1-\epsilon}$-hard).</p>

<p>Original answer:
Path Coloring can be reduced to graph coloring in the obvious way (make a vertex for each path, add an edge if two paths intersect). If the underlying graph in path coloring is allowed to be a grid there is also a reduction in the opposite direction, which means that in this case the problems are equivalent. The reduction does not change the number of colors, so all hardness of approximation results for graph coloring carry over to this case of path coloring, and therefore also when the underlying graph can be any graph.</p>

<p>I heard this reduction in a talk a while ago, but I can't seem to be able to find a reference, so I'll sketch it here.</p>

<p>We start with a graph $G(V,E)$ on $n$ vertices and the question is if it can be colored with $k$ colors. Construct a graph $H$ which is a $n\times ({n\choose 2}+1)$ grid (we index the rows by the vertices of $G$ and the columns by pairs of vertices of $G$). We will add one path in this graph for each vertex of $G$. Initially, each of these paths is simply a row of the grid, so no two of them intersect and they all have length $n\choose 2$. The idea here is that we will use the $n\choose 2$ edges between columns of the grid to simulate the edges of the original graph. For example, if vertex $i$ is connected to vertex $j$ in $G$, with $i&lt;j$, take the path that runs through row $i$ and re-route it as follows: the path now goes from vertex $(i,(i,j))$ to $(j,(i,j))$, then it uses the next edge on the $j$-th row and then it goes back to row $i$. This creates an intersection between paths $i$ and $j$, but no other edge intersections. By adding the rest of the edges of $G$ this way, the resulting instance is $k$-colorable iff $G$ is.</p>

CC BY-SA 3.0
2012-12-15T16:36:56.477Z
2012-12-18T13:07:48.230Z
2012-12-18T13:07:48.230Z
Michael Lampis
<p>Path coloring is the problem of coloring a set of paths R in graph G, in such a way that any two paths of R which share an edge in G receive different colors.</p>

<p>We know that coloring a set of paths with the minimum number of colors is in $\sf{P}$, if the underlying graph is also a path. It is known that path coloring in trees is $\sf{NP}$-hard. There is a greedy algorithm by Raghavan and Upfal (Efficient routing in all-optical networks,  STOC 1994), which colors any set of paths of load $L$ on an undirected tree using at most $3L/2$ colors. This bound is tight, since there exists a set of undirected paths on an undirected binary tree, which requires at least $3L/2$ colors.</p>

<p>What are the results known for general graphs, both approximation algorithms and lower bounds?</p>

CC BY-SA 3.0
2012-11-09T17:18:27.687Z
What is the definition of path coloring?  Also, would you please provide more info (a link very be especially appreciated) about Raghavan and Upfal's algorithm?
Yixin Cao
CC BY-SA 3.0
2012-11-09T17:51:58.567Z
The first problem in Wikipedia entry: http://en.wikipedia.org/wiki/Path_coloring
Arindam Pal
CC BY-SA 3.0
2012-11-09T18:23:03.983Z
It would be even more helpful to make the definition inline.
Suresh Venkat
CC BY-SA 3.0
2012-11-10T02:11:58.163Z
Added the definition as well as the reference to Raghavan and Upfal paper.
Arindam Pal
CC BY-SA 3.0
2012-11-10T03:25:11.513Z
The following papers have relevant results http://www.springerlink.com/content/0yuby3h98xtyd0ng/ and http://www.sciencedirect.com/science/article/pii/S0022000005000735 and http://ect.bell-labs.com/who/ylz/2006.coloring4.pdf
Chandra Chekuri
<cc.complexity-theory><ds.algorithms><graph-theory><approximation-algorithms><graph-colouring>
Path coloring in general graphs
Arindam Pal
# Path coloring in general graphs

(Asked by: username_0 on 2012-11-09)

Path coloring is the problem of coloring a set of paths R in graph G, in such a way that any two paths of R which share an edge in G receive different colors.

We know that coloring a set of paths with the minimum number of colors is in $\sf{P}$, if the underlying graph is also a path. It is known that path coloring in trees is $\sf{NP}$-hard. There is a greedy algorithm by Raghavan and Upfal (Efficient routing in all-optical networks, STOC 1994), which colors any set of paths of load $L$ on an undirected tree using at most $3L/2$ colors. This bound is tight, since there exists a set of undirected paths on an undirected binary tree, which requires at least $3L/2$ colors.

What are the results known for general graphs, both approximation algorithms and lower bounds?

**Tags:** cc.complexity-theory, ds.algorithms, graph-theory, approximation-algorithms, graph-colouring

> **Comments:**
> **username_1**: What is the definition of path coloring?  Also, would you please provide more info (a link very be especially appreciated) about Raghavan and Upfal's algorithm?  
> **username_0**: The first problem in Wikipedia entry: http://en.wikipedia.org/wiki/Path_coloring  
> **username_2**: It would be even more helpful to make the definition inline.  
> **username_0**: Added the definition as well as the reference to Raghavan and Upfal paper.  
> **username_3**: The following papers have relevant results http://www.springerlink.com/content/0yuby3h98xtyd0ng/ and http://www.sciencedirect.com/science/article/pii/S0022000005000735 and http://ect.bell-labs.com/who/ylz/2006.coloring4.pdf  

---

## 1 answers

### Answer by username_4 on 2012-12-15. Score: 2

Edit: In the end I did find a reference for the reduction I remembered. It is given in [Edge intersection graphs of single bend paths on a grid](http://www.cs.haifa.ac.il/~marinal/Networks.pdf) by Golumbic, Lipshteyn, and Stern. So, to sum up, the class of graphs obtained as intersections of paths on a grid contains all graphs. Therefore, path coloring on grids is as hard to approximate as graph coloring ($n^{1-\epsilon}$-hard).

Original answer:
Path Coloring can be reduced to graph coloring in the obvious way (make a vertex for each path, add an edge if two paths intersect). If the underlying graph in path coloring is allowed to be a grid there is also a reduction in the opposite direction, which means that in this case the problems are equivalent. The reduction does not change the number of colors, so all hardness of approximation results for graph coloring carry over to this case of path coloring, and therefore also when the underlying graph can be any graph.

I heard this reduction in a talk a while ago, but I can't seem to be able to find a reference, so I'll sketch it here.

We start with a graph $G(V,E)$ on $n$ vertices and the question is if it can be colored with $k$ colors. Construct a graph $H$ which is a $n\times ({n\choose 2}+1)$ grid (we index the rows by the vertices of $G$ and the columns by pairs of vertices of $G$). We will add one path in this graph for each vertex of $G$. Initially, each of these paths is simply a row of the grid, so no two of them intersect and they all have length $n\choose 2$. The idea here is that we will use the $n\choose 2$ edges between columns of the grid to simulate the edges of the original graph. For example, if vertex $i$ is connected to vertex $j$ in $G$, with $i


---

