Algorithm Journal: Graph Colouring with k=2

You’re given an array of rivals:

rivals = ["A", "B", "C"]

And a list of matches between two rivals represented in tuple form:

matches = [("A", "B), ("B", "C")]

Assign a label (either “good” or “bad”) to each rival, so that there is no match where both rivals have the same label.

Initial thoughts on the solution

At a first glance, it sounds very similar to the Graph Colouring problem. In fact I believe it is no different from it, although it is a special case of the graph colouring problem with 2 as the number of colours.

My solution to the problem:

rivals = ["A", "B", "C"]

matches = [("A", "B), ("B", "C")]

def solve():
  labels = {}  # e.g. { "A": "good", "B": "bad" ... }
  
  # key is a rival, and value is a set of other rivals the key rival 
  # has a match with. E.g. { "A": {"B"}, "B": {"A", "C"}, "C": {"B"} }
  graph = {}  

  # construct the graph
  for match in matches:
    if match[0] not in graph:
      graph[match[0]] = set()
    if match[1] not in graph:
      graph[match[1]] = set()

    graph[match[0]].add(match[1])
    graph[match[1]].add(match[0])

  
  for match in matches:
    # the _label function is going to have a recursive ripple effect
    # and solve the problem recursively
    # but it is still necessary to iterate through
    # all matches and call _label on them
    # because if the graph is disconnected and have
    # many subgraphs,
    # calling _label on only one match would only
    # solve the problem for one subgraph
    # example: 
    # matches=[("A", "B"), ("B", "C"), ("Z", "X)] 
    # where we have two separate subgraphs

    arbitrary_label = "good"
    _label(match[0], arbitrary_label, graph, labels)

  return labels


def _label(current_rival, label, graph, labels):
  if current_rival in labels:
    # already processed and labeled
    return

  new_label = "bad"
  if label == "bad":
    new_label = "good"
  
  labels[current_rival] = label
  matching_rivals = graph[current_rival]
  
  for matching_rival in matching_rivals:
    labels[matching_rival] = new_label 
    _label(matching_rival, new_label, graph, labels)

I haven’t thought about how to solve the problem where the number of colours/labels k > 2. I could always rely on backtracking, and build a tree of the whole candidate solution space. However even if I have the candidate solution space, I’d need to check if a candidate solution is a valid one which is another hard problem on its own. The fact that the number of colours here is 2 makes the solution much easier, as the general solution to the graph colouring problem appears to be NP-complete.