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

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

"GCRhoads" <rhoads@xxxxxxxxxxxxxxx> writes:


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.

Ah, thank you. this makes sense. Fortunately, the important part of
the exercise was not determining the asymptotic complexity. So, I was
beguiled by the apparent simplicity of the algorithms into accepting
their hand-waving claims of low complexity. That doesn't mean their
aren't factual errors in their algorithms (or also errors in their
analysis of them). But, it does mean that I'm happier knowing that I
didn't lead them into a cul-de-sac. Now, I can write up my review of
the problem.

BTW, your insight does highlight one interesting aspect of the problem
that the students solved. When atempting to determine how to recolor
the vertexes, we have slightly more information than conflict/don't
conflict. Since the vertexes represent inputs that drive a DFA, when
we find two verticies where one needs recolored, it means that there
is a state in the DFA where the inputs transition to different
outbound states. One can use that to guide the recoloring. If there
are inputs which need to be recolored, then those inputs have
transitions from some common state to distinct target states.
However, one can [re]color transtions to the same distinct target
state with the same [new] color. Thus, the shape of the DFA guides
the coloring.

Is it possible that the information contained in that DFA guides the
coloring process and lowers its complexity. That wouldn't suprise me
too much, since it is well known that constructing a DFA from an NFA
can result in an exponential increase in the number of states. Thus,
coloring the inputs to an NFA could be NP-complete, while the
restrictions on a DFA, make coloring the inputs to a DFA polynomial in
bound, because the hard cases (of graphs to color) require exponential
sized DFAs to represent. The complexity didn't go away, it is just
moved to a different part of the problem.

That is if you have a hard to color graph of inputs, those might
correspond well to the transitions in an NFA. However, as you create
the DFA from the NFA, you exponentially expand the size of the
problem. Now, if you are measuring the size of the problem based on
the state machine size, it looks like the complexity has been
lowered. However, that's because the NFA to DFA construction process
has already done an exponential growth in the "apparent" input size
and the DFA size is not related to the original graph size in the same
way the NFA would have been, it is exponentially larger. Thus, as the
interference graph for an NFA grows linearly, the corresponding DFA
grows exponentially, and we have a "bookkeeping" error in how we are
accounting for problem size.

Does that make sense?
-Chris
.

Relevant Pages

  • Re: FOUR COLOR THEOREM
    ... The example present a coloring of the graph which experiences an ... The impasse is due to the following situation: ... resulting graph demands that v_2 and/or v_4 be recolored. ... the recoloring of G will eventually lead to a proper 4-coloring ...
    (sci.math)
  • Re: NFA to DFA
    ... what looks like some kind of graph based automaton. ... here's how I'd start with a DFA ... there are two ways that you could proceed with the NFA -> DFA conversion. ... transition arrows from each state in the set s1, and appending the endpoints of those ...
    (comp.lang.cpp)
  • Re: Is this a form of Data Flow Analysis, and what is the proper way solution to the problem?
    ... after doing some more reading on DFA, ... Data flow analysis is not generally ... It's easier if you construct the basic blocks and the control graph ... You said in your original post: ...
    (comp.compilers)