debugMinor
Graph coloring with fixed-size color classes
Viewed 0 times
coloringgraphwithsizecolorclassesfixed
Problem
I'm interested in coloring a graph, but with slightly different objectives than the standard problem. It seems like the focus of most graph-coloring algorithms (DSATUR etc) is to minimize the number of color classes used.
My goal, in contrast, is to maximize the number of color classes of fixed size N.
As a concrete example, say I have a graph with
I figure I can solve this problem with a Greedy Algorithm, but it won't be optimal. Or I could model this in a constraint solver, but it might not employ some clever graph-specific tricks that could come in handy.
Does this specific problem have a name? Or an established algorithm to solve it? Thank you!
EDIT:
It was rightfully pointed out that my question is ambiguous! I can explain much more thoroughly, my apologies for the confusion.
First, let me define the size of a color class. I've seen this terminology elsewhere but might be using it incorrectly. The size of a color class is the number of nodes assigned to that color. I will denote this:
Now, to define a fixed size color class. This is a color class with size
As far as the optimization objective: I want to color a graph to maximize the number of size-30 color classes. If you'll permit me some Python pseudocode:
To complete the example, take these two possible colorings of a graph with 100 nodes. Each number represents the number of nodes colored by that color:
```
Coloring 1: {55, 25, 20} (n_size_30_colors = 0)
Colo
My goal, in contrast, is to maximize the number of color classes of fixed size N.
As a concrete example, say I have a graph with
100 nodes, and I'd like to color the graph with color classes of size N = 30. With an optimal algorithm and the right graph, I could find 3 such groups that color 90 total nodes, with 10 nodes left over. A lesser algorithm might only produce 2 such groups, with 40 nodes left over that cannot be colored with a size-30 color class.I figure I can solve this problem with a Greedy Algorithm, but it won't be optimal. Or I could model this in a constraint solver, but it might not employ some clever graph-specific tricks that could come in handy.
Does this specific problem have a name? Or an established algorithm to solve it? Thank you!
EDIT:
It was rightfully pointed out that my question is ambiguous! I can explain much more thoroughly, my apologies for the confusion.
First, let me define the size of a color class. I've seen this terminology elsewhere but might be using it incorrectly. The size of a color class is the number of nodes assigned to that color. I will denote this:
size(C_i) = .Now, to define a fixed size color class. This is a color class with size
N. To use the example above, I'm interested in colorings with colors such that size(C_i) = 30.As far as the optimization objective: I want to color a graph to maximize the number of size-30 color classes. If you'll permit me some Python pseudocode:
n_size_30_colors = len([c for c in colors if size(c) == 30])
maximize(n_size_30_colors)To complete the example, take these two possible colorings of a graph with 100 nodes. Each number represents the number of nodes colored by that color:
```
Coloring 1: {55, 25, 20} (n_size_30_colors = 0)
Colo
Solution
This problem is NP-hard: it is at least as hard as independent set. In particular, if you want to know whether there exists an independent set of size $N$, ask for a coloring with as many colors of size $N$; if you find any coloring where a single color occurs $N$ times, you know there's an independent set of size $N$. So, you should not expect any efficient algorithm for this problem that works on all problem instances.
One plausible approach is to use a ILP solver. You can define zero-or-one variables $x_{v,c}$, where $x_{v,c}=1$ means that vertex $v$ is assigned color $c$. Then it is easy to express the requirement that a color $c$ be assigned to exactly $N$ vertices: we require $\sum_{v \in V} x_{v,c} = N$. The constraint that two adjacent vertices $v,w$ be assigned different colors can be expressed by $x_{v,c} + x_{w,c} \le 1$ for all $c$, and that each vertex $v$ receive a color by $\sum_c x_{v,c} = 1$. Without loss of generality, to test whether it is possible to have $k$ colors be assigned to $N$ vertices, you can constrain the first $k$ colors to have $N$ vertices and put no constraints on the remaining colors. Then, use binary search on $k$ to find the largest $k$ for which a solution exists.
Another plausible approach is to use a SAT solver. You could define variables $x_{v,c}$, where if $x_{v,c}$ is true then vertex $v$ is assigned color $c$, and express your constraints in SAT. You can require that color $c$ be assigned to exactly $N$ vertices, by requiring that $N$ out of the variables $x_{\cdot,c}$ are set to true (see Encoding 1-out-of-n constraint for SAT solvers and links for methods). Otherwise, this is similar to using an ILP solver.
These might work if $N$ is small enough and the graph is small enough, but eventually will run into exponential behavior once the problem gets large enough.
One plausible approach is to use a ILP solver. You can define zero-or-one variables $x_{v,c}$, where $x_{v,c}=1$ means that vertex $v$ is assigned color $c$. Then it is easy to express the requirement that a color $c$ be assigned to exactly $N$ vertices: we require $\sum_{v \in V} x_{v,c} = N$. The constraint that two adjacent vertices $v,w$ be assigned different colors can be expressed by $x_{v,c} + x_{w,c} \le 1$ for all $c$, and that each vertex $v$ receive a color by $\sum_c x_{v,c} = 1$. Without loss of generality, to test whether it is possible to have $k$ colors be assigned to $N$ vertices, you can constrain the first $k$ colors to have $N$ vertices and put no constraints on the remaining colors. Then, use binary search on $k$ to find the largest $k$ for which a solution exists.
Another plausible approach is to use a SAT solver. You could define variables $x_{v,c}$, where if $x_{v,c}$ is true then vertex $v$ is assigned color $c$, and express your constraints in SAT. You can require that color $c$ be assigned to exactly $N$ vertices, by requiring that $N$ out of the variables $x_{\cdot,c}$ are set to true (see Encoding 1-out-of-n constraint for SAT solvers and links for methods). Otherwise, this is similar to using an ILP solver.
These might work if $N$ is small enough and the graph is small enough, but eventually will run into exponential behavior once the problem gets large enough.
Context
StackExchange Computer Science Q#132259, answer score: 4
Revisions (0)
No revisions yet.