Re: A restricted case of graph coloring, is this a known problem?
- From: "GCRhoads" <rhoads@xxxxxxxxxxxxxxx>
- Date: 23 Feb 2007 18:39:55 -0800
On Feb 23, 11:49 am, Chris F Clark <c...@xxxxxxxxxxxxxxxxxxxx> wrote:
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
In the students' algorithm, how is the recoloring done? If their
algorithm
performs n^2 recoloring steps, then each recoloring step must be done
in constant time to get an O(n^2) algorithm and it does not seem
possible
to this in constant time. Suppose that at some point you find a state
of
the DFA that takes two distinct transitions on two like-colored
characters.
Now you have to move one of those two characters out that color set
and
into some other, possibly new, color set. But exactly where do you
move
it? You can simply give it a new color in constant time but this will
not
in general minimize the number of colors; it may be possible to assign
it the same color as some other set of characters without causing a
conflict. The only way to tell is to examine the transitions from
each
state to see if there is a conflict with each of the other color sets,
and
you can't do that in constant time.
.
- Follow-Ups:
- Re: A restricted case of graph coloring, is this a known problem?
- From: Chris F Clark
- Re: A restricted case of graph coloring, is this a known problem?
- References:
- A restricted case of graph coloring, is this a known problem?
- From: Chris F Clark
- A restricted case of graph coloring, is this a known problem?
- Prev by Date: A restricted case of graph coloring, is this a known problem?
- Next by Date: Re: language theory regarding Perl/Ruby in universities ?
- Previous by thread: A restricted case of graph coloring, is this a known problem?
- Next by thread: Re: A restricted case of graph coloring, is this a known problem?
- Index(es):
Relevant Pages
|
