Consider the following adaptation of the traveling salesman problem: Given a com

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?blue?blue?blue?red

is valid but

red?blue?blue?blue?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 v0 and at each step, simply choose the vertex v1 that minimizes d(v0,v1). However, keep a record of the colors of vi, vi?1, and vi?2 at each step, and if the optimal choice of the next vertex vi+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.)

Explanation / Answer

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?.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.