Re: A restricted case of graph coloring, is this a known problem?
- From: klaus hoffmann <nospam@xxxxxxxxxxxx>
- Date: Sun, 25 Feb 2007 17:02:39 +0100
Chris F Clark 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
Graph cololoring may be NP-complete. If you consider interval graphs, it has complexity n*log(n). In your special case you may attach an ordered list of transitions to each character, sort the characters by this lexical list and merge characters with equal lists. This can be done in linear time with respect to the transition matrix if you use radix sorting.
hth
Klaus
.
- 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: Turing Machine
- Next by Date: Re: On the General Construction for Kleene star in Context-Free Language
- Previous by thread: Re: 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
|
