# Coloring graphs with reinforcement learning

I am trying to build an RL agent to solve the NP-hard problem graph coloring. The problem is quite challenging.

### The environment

To preserve the scalability of the algorithm, providing the agent with the whole graph wouldn't be a good idea. Therefore, the input for the agent would be a window of embeddings.

More precisely, first, I would apply an embedding to the graph to generate fixed-size vectors to every vertex in the graph (thus, every vertex in the graph is represented as a vector that contains some information about its neighborhood and position in the graph).

Second, the agent will get a window of the embedding. For example, when coloring vertex number $$17$$, the input would be the $$2n$$ vectors from vertex $$17-n$$ to $$17+n$$, to give the agent more local information.

My biggest problem is how the agent should be. Technically, the problem is the action space dimension. For a given graph, the maximal number of colors is the number of vertices which varies from graph to graph (losing the scalability). Plus, the possible actions at each state varies with the history of the coloring. The possible colors for a given state (or node) are all the used colors eliminating the connected colors and adding the possibility of a new color, that is, for vertex $$56$$, the agent has already used the first $$40$$ colors $$\{0, 1, 2, 3, \dots,40 \}$$, and node $$56$$ is connected to some neighbors already colored with $$\{14, 22, 40 \}$$, the possible colors are $$\{0,1, \dots, 40 \}- \{14, 22, 40 \} + \{41\}$$.