Algorithm for Identifying Consistently Colored Node Subsets in Near-Optimal Graph Colorings

Question

I am currently working on a problem related to graph coloring and subset identification. Given an undirected graph, I am interested in finding subsets of nodes that exhibit a consistent coloring pattern across optimal or near-optimal graph colorings, meaning that all the nodes in a subset share the same color in every optimal coloring of the graph. Since the problem seems to be computationally challenging, I am open to approximation algorithms. My goal is to identify these subsets in a way that provides insights into the coloring behavior of the graph.

More formally, let's denote the problem as follows:

Given an undirected graph G(V, E), I am looking for an algorithm that can identify subsets of nodes S_1, S_2, ..., S_k (where k is unknown a priori) with the following property: For any optimal (or close-to-optimal) graph coloring of G, all nodes within each subset S_i should be assigned the same color.

Since finding exact solutions to this problem might be computationally infeasible, I am particularly interested in approximation algorithms that can efficiently generate some of the subsets (or partial subsets) satisfying the above property.

I would appreciate any insights, references, or algorithmic approaches that could help address this problem. Additionally, if there are related works or research directions that touch upon similar concepts, I would be grateful to learn about those as well.

Thank you in advance for your assistance!

Answer 1

I can suggest an approach that might be worth trying.

1. Identify several optimal colorings $C_1,\dots,C_m$ of $G$.

2. Find subsets $S_1,\dots,S_\ell$ such that, for each $C_j$, all nodes within each $S_i$ are assigned the same color.

3. For each $S_i$, test whether there exists an optimal coloring of $G$ that does not assign all nodes in $S_i$ the same color. If yes, add that coloring to the list of $C_j$'s. If no, output $S_i$ (and you never need to test it again).

4. Go to step 2.

Now you just need a way to implement each of those steps. They can be done as follows:

1. You can find an optimal coloring of $G$ using a SAT solver.

2. You can find sets $S_i$ as follows. Build a new graph $G'$ with an edge $(u,v)$ if $u,v$ are assigned the same color in all of $C_1,\dots,C_m$. Then, find maximal cliques of $G'$; each such maximal clique is a candidate for a set $S_i$. You can find such cliques using a SAT solver, or with https://en.wikipedia.org/wiki/Clique_problem#Algorithms.

3. You can test whether there exists an optimal coloring of the desired form using a SAT solver.

So, by repeatedly invoking a SAT solver, I expect you should be able to find sets of the form that you're looking for. In principle, this loop might require iterating many times; and in principle, each step could well take exponential time. But if your graph is not too large, it is possible that in practice you might still be able to obtain useful results in a reasonable amount of time, due to the effectiveness of SAT solvers.