Finding equally-sized mutually exclusive complete subgraphs within a graph whose union is the entire graph

user_15483407 0
Viewed 70

INPUT
Undirected graph G with n vertices and an integer k such that k divides n.
The set of all vertices will be denoted by V.

OUTPUT
A set S of sets of vertices such that:

  1. S has k elements
  2. Each element of S is a complete subgraph in G (all vertices in each element share an edge with each other in G)
  3. All elements of S are mutually exclusive (the elements have no vertices in common with each other)
  4. The union of all the elements of S is equal to V
  5. All elements of S have cardinality n / k

BACKGROUND
I run a small play reading group and we like to read larger plays sometimes. I want to cast a large play for a small group in such a way that a single person won't be playing a set of characters that share scenes with each other. I realized that this problem could be formulated in graph theory, and I'm curious as to what a good solution looks like.

undirected-graph subgraph graph-theory algorithm
1 Answers

This problem is basically equivalent to graph coloring. Graph coloring gives us a graph and asks us to give each node a color such that no edge has identically colored endpoints. Here I assume that the nodes would be roles, the edges would be roles that appear together in at least one scene, and colors would be people playing the roles, and you want specifically a coloring that uses exactly k colors (for k people).

Graph coloring is NP-hard, but unless the graph is huge, a constraint programming solver (e.g., CP-SAT) should have an easy time with it, and additionally handle an optimization objective like (e.g.) maximizing the minimum number of lines that each person has.

user_21446690
Related