A restricted case of graph coloring, is this a known problem?

I recently assign a set of summer intern candidates a problem that can
be solved by graph coloring, but all the students came up with n**2 or
n**3 solutions using a greedy approach.

Now, as I recall, general graph coloring is np-complete. So, the
question I need to have answered is whether I constrained this problem
to a set where it can be solved in polynomial time or whether the
students have simply found a partial solution.

Here is a quick sketch of the problem. You have two machines that you
run in a pipelined fashion. The first machine executes a translate
instruction (a linear map of values in the set to other values). The
second machine executes a DFA and returns whether it accepts or
rejects the input string. The goal is to minimze the size of states
in the DFA by remapping input characters (using the translation
machine) into a smaller input range.

For example, if the machine has transitions on the range a-f, we might
represent those characters by 1, then we might represent the range 0-9
by 2, and A-F by 3. and G-Z by 4, etc. Thus, instead of having lots
of similar transitions to the same state, we have a much smaller set
of transitions and a much smaller alphabet. If there are only 16
distinct ranges used in the DFA, we might use a 4 bit alphabet and
states would have at most 16 transitions.

The basic idea is you want to find sets of characters which always
make their transitions together. That is, for all states in the DFA,
if one character in the set makes a transition to some other state,
every other character in the set makes that same transition.

This can be represented as a graph coloring problem. The characters
are the veriticies of the graph that we wish to color. An edge is
drawn between two characters if in any state, the two characters make
a transition to different states. The edge, of course, prevents the
two characters from being given the same color. Once, you have
"drawn" the graph, one simply applies the coloring algorithm to it and
has a solution. The colors are what we make the translation machine
output and the minimal coloring minimizes the size of the DFA.

Now, the solution proposed by the students is generally a greedy
algorithm that starts with all the characters being one colored, and
splits (recolors distinctly) any sets of characters that have a
different transition for some state. The algorithm loops over states,
and transtions leaving a state, and thus has roughly n**2 perfromance.

So, is this solution optimal? And if so, why do I not need a general
graph coloring algorithm to solve it? If not, what kind of DFA is a
counter example that shows that the greedy algorithm will assign too
many colors?

Thanks,
-Chris
.

Relevant Pages

  • Re: A restricted case of graph coloring, is this a known problem?
    ... Now, as I recall, general graph coloring is np-complete. ... in the DFA by remapping input characters (using the translation ... For example, if the machine has transitions on the range a-f, we might ... represent those characters by 1, then we might represent the range 0-9 ...
    (comp.theory)
  • Re: A restricted case of graph coloring, is this a known problem?
    ... Now, as I recall, general graph coloring is np-complete. ... in the DFA by remapping input characters (using the translation ... For example, if the machine has transitions on the range a-f, we might ... represent those characters by 1, then we might represent the range 0-9 ...
    (comp.theory)
  • Re: A restricted case of graph coloring, is this a known problem?
    ... Now, as I recall, general graph coloring is np-complete. ... For example, if the machine has transitions on the range a-f, we might ... represent those characters by 1, then we might represent the range 0-9 ... one simply applies the coloring algorithm to it and ...
    (comp.theory)
  • Re: Performance Question C++/CLI
    ... if there are less than n transitions per second, ... It all depends on the amount of time ... characters a second most of the time, so that's 8 transitions, meanwhile, ... It'll probly work out ...
    (microsoft.public.dotnet.languages.vc)