Seeking Efficient Approximation Algorithm for Adaptation of TSP

Question

Consider the following adaptation of the traveling salesman problem:

Given a complete, undirected graph $G$ with nonnegative edge weights, color each vertex either red or blue. Find the shortest path that visits all vertices exactly once (does not need to return to starting vertex), but does not visit vertices of the same color more than 3 times in a row (i.e. the path

$$red \to blue \to blue \to blue \to red$$

is valid but

$$red \to blue \to blue \to blue \to blue$$

is not. Assume that there are the same number of red and blue vertices.

I'm trying to come up with an algorithm to at least approximate a shortest path given this constraint. My initial thought was the following (besides simply trying all $|V|!$ different paths):

Greedy Approach: Choose a starting vertex $v_0$ and at each step, simply choose the vertex $v_1$ that minimizes $d(v_0, v_1)$. However, keep a record of the colors of $v_{i}$, $v_{i-1}$, and $v_{i-2}$ at each step, and if the optimal choice of the next vertex $v_{i+1}$ violates the color constraint, choose the next best vertex.

The only problem I see with this is that you can 'run out' of vertices of a given color. That is, you could reach a point where there are more than $3$ vertices remaining, but they are all of the same color. This would make it impossible to complete the path.

My Question: Does anyone have any suggestions on algorithms to try? Maybe a modification to my suggested greedy approach to make it complete, or another paradigm all together?

(I know that this problem is $NP$-complete - that's why I'm seeking an approximation algorithm.)

Answer 1

Since this is your exercise, it sounds like you are only looking for a hint or an approach. So, here is a hint/approach.

Let $M$ be a DFA (deterministic finite-state automaton) that recognizes all legal sequences of colors, where a sequence is legal if it doesn't contain the same color three times in a row.

Construct a new, bigger graph $G'$, formed by a "product construction" of $G$ and $M$. The number of vertices in $G'$ will be at most the number of vertices of $G$ times the number of states of $M$, so $G'$ will be bigger but not too much bigger.

Now think about what you can do with this $G'$. Try translating your original problem into some question about $G'$.