Finding a path crossing minimum number of distinct colors

Given a set $\cal D$ of unit disks in the plane and a set $C$ of colors. Every disk in $\cal D$ is colored with one of the colors in $C$. Note that multiple disks may be colored with the same color. Every color $c_i \in C$ is associated with a weight $w_i$.

for every path $p$ in the plane, we define the weight of $p$ as the sum of the weights of the colors that at least one of the circles with that color is crossed by $p$.

In addition, two points $s$ and $t$ is given in the plane and the goal is to find a path between $s$ and $t$ with the minimum total weight. What is the best approximation factor we can guarantee?

• What did you try? Where did you get stuck? – David Richerby Dec 11 '16 at 10:39
• Currently, we know that the problem is $NP$-hard and admits no approximation better than $\log n$ where $n$ is the number of unit diks. – Z M Dec 11 '16 at 13:33

1 Answer

For a constant number of colors, the problem can be solved by considering all possible subsets of colors. The rest can be solved using a shortest path with memoization.

You can reduce set cover to this problem: Build a grid with $m+2$ rows and $n+2$ columns. Also assume all points in one column are connected, but connect the points in rows based on the following rule:

Each column represents a member of the universal set and each row a set. The boundary is a color with weight zero. Let $s$ be the leftmost uppermost point and $t$ be the rightmost and lowest point and remove the other two corners of the grid. Color the point $i,j$ with color $i$ if set $S_i$ contains $u_j$ and remove it otherwise. The minimum weight path in this graph is the same as the minimum set cover.

This subset of a grid, is a unit disk graph: allow the columns to be $cn$ apart from each other, where $c$ is the vertical distance between the first row and last row. So $\theta(\log n)$ is tight.

• Thanks. Your construction reveals the negative side: no approximation better than $\log(n)$ is possible. Do you think any approximation factor can be guaranteed in polynomial time? – Z M Dec 12 '16 at 7:06
• You can convert every unit disk graph into a grid: – Sepid Dec 12 '16 at 14:53
• en.wikipedia.org/wiki/Unit_disk_graph#Computational_complexity – Sepid Dec 12 '16 at 14:53