patternMinor
Equivalent Colorings of Graphs
Viewed 0 times
graphscoloringsequivalent
Problem
Call two proper graph colorings equivalent if one can be obtained from the other by a permutation of the colors.
In other words, they are the "same" coloring.
I'm interested in finding proper non-equivalent colorings.
Of course, the decision problem of determining whether or not there is such a non-equivalent coloring given one is NP-complete.
Are there FPT, approximation, etc. algorithms for finding such a coloring if one exists?
I am currently running a randomized greedy coloring algorithm, which does often succeed in finding a proper coloring - however, I am unsure of when it actually produces a non-isomorphic one.
If it is helpful, I'm working with graphs which are essentially $k$-trees.
In other words, they are the "same" coloring.
I'm interested in finding proper non-equivalent colorings.
Of course, the decision problem of determining whether or not there is such a non-equivalent coloring given one is NP-complete.
Are there FPT, approximation, etc. algorithms for finding such a coloring if one exists?
I am currently running a randomized greedy coloring algorithm, which does often succeed in finding a proper coloring - however, I am unsure of when it actually produces a non-isomorphic one.
If it is helpful, I'm working with graphs which are essentially $k$-trees.
Solution
Many existing heuristics for graph coloring can work even if you specify the colors of a few vertices. So, here is one plausible algorithm you could use:
We are given an existing coloring $C$. Pick two vertices $v,w$ randomly. We are going to assign colors for $v,w$ (in the new coloring), leave the other vertices unassigned, and use some existing graph coloring heuristic to extend this to a coloring for the whole graph. If $C(v)=C(w)$, assign $v,w$ two different colors in the new coloring (any two, it doesn't matter which two colors you use). If $C(v)\ne C(w)$, assign $v,w$ the same color in the new coloring (any color, it doesn't matter which you pick). Then extend this to a coloring for the new graph.
If this finds a coloring, then you're guaranteed that the new coloring will be non-equivalent to the old one. Moreover, if there exists a non-equivalent coloring, you're guaranteed to be able to find it with at most polynomially many invocations of this procedure. In particular, if $C'$ is non-equivalent, there must exist some pair of vertices $v,w$ where $C(v)=C(w)$ and $C'(v) \ne C'(w)$, or where $C(v) \ne C(w)$ and $C'(v) = C'(w)$. Therefore, if you repeat the above procedure for all pairs $v,w$ of vertices, at least one of those iterations should find a new non-equivalent coloring.
So, this might be one reasonable approach, if you want to find a new non-equivalent coloring once. On the other hand, if you are given $m$ existing colorings and want to find a $m+1$st non-equivalent coloring, that looks more complicated.
We are given an existing coloring $C$. Pick two vertices $v,w$ randomly. We are going to assign colors for $v,w$ (in the new coloring), leave the other vertices unassigned, and use some existing graph coloring heuristic to extend this to a coloring for the whole graph. If $C(v)=C(w)$, assign $v,w$ two different colors in the new coloring (any two, it doesn't matter which two colors you use). If $C(v)\ne C(w)$, assign $v,w$ the same color in the new coloring (any color, it doesn't matter which you pick). Then extend this to a coloring for the new graph.
If this finds a coloring, then you're guaranteed that the new coloring will be non-equivalent to the old one. Moreover, if there exists a non-equivalent coloring, you're guaranteed to be able to find it with at most polynomially many invocations of this procedure. In particular, if $C'$ is non-equivalent, there must exist some pair of vertices $v,w$ where $C(v)=C(w)$ and $C'(v) \ne C'(w)$, or where $C(v) \ne C(w)$ and $C'(v) = C'(w)$. Therefore, if you repeat the above procedure for all pairs $v,w$ of vertices, at least one of those iterations should find a new non-equivalent coloring.
So, this might be one reasonable approach, if you want to find a new non-equivalent coloring once. On the other hand, if you are given $m$ existing colorings and want to find a $m+1$st non-equivalent coloring, that looks more complicated.
Context
StackExchange Computer Science Q#91737, answer score: 5
Revisions (0)
No revisions yet.