4
$\begingroup$

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!

$\endgroup$
3
  • 3
    $\begingroup$ Welcome to CS.SE! What is meant by "maximize the number of color classes of fixed size N"? That sounds to me like it is contradictory; on the one hand, you want to maximize the number of colors, on the other hand it is fixed. I suspect I am not understanding what you have in mind. What's meant by the "size" of a "color class"? I'm also confused by "nodes left over"; normally in graph coloring we require to assign a color to each node. Can you give a careful specification of the task, i.e., the inputs to the algorithm and what output it should produce? Can you edit? $\endgroup$ – D.W. Nov 15 '20 at 7:04
  • $\begingroup$ Thank you for the helpful feedback D.W! I've added an edit, I hope it helps. $\endgroup$ – Raphie Palefsky-Smith Nov 15 '20 at 21:04
  • 2
    $\begingroup$ Some bad news: This problem is NP-hard, since Independent Set can be trivially reduced to it. A graph contains an IS of size $k$ iff treating it as an instance of your problem with $N=k$ gives a solution $\ge 1$. $\endgroup$ – j_random_hacker Nov 15 '20 at 22:14
4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ This is such a fantastic answer! The connection to Independent Set is particularly cool - it was not obvious to me until you pointed it out. As you and j_random_hacker in the comments above have mentioned, this is NP-hard to solve optimally. But perhaps there's a good approximation out there? I'm starting to try the ILP approach regardless; here's hoping my graph is small enough to avoid runaway runtimes. $\endgroup$ – Raphie Palefsky-Smith Nov 16 '20 at 15:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.