Graph coloring with fixed-size color classes

Question

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 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) = <number of nodes colored 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)
Coloring 2: {30, 30, 20, 20} (n_size_30_colors = 2)
Coloring 3: {30, 30, 30, 10} (n_size_30_colors = 3)

Even though Coloring 1 uses fewer colors, Coloring 3 is optimal because it returns the most size-30 color classes. The size-55 color class in Coloring 1 is "wasteful" in that those 25 extra nodes are not useful; an optimal solution for this problem would distribute those nodes to other color classes, hopefully yielding more size-30 colors.

I hope this clarifies things somewhat, and thanks again!

Answer 1

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.