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

Question

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.

Henkel

The way you've described it (including the title), there can be no edges between (vertices in) any pair of elements of S. Consequently a solution can exist only if G is disconnected with k or more components. Is that what you intend? If so, this is better characterized as bin packing. – Rabush

You have people, characters and scenes. Characters to scenes is a fixed bi-partite graph. You want a bi-partite graph from people to characters subject to the constraints. Right? Can you explain how that maps to your input and output definition? N? k? – Quinate

I suspect this problem is NP-complete (it seems somewhere between clique and set cover). I don't have a proof, though. If I can come up with one, I'll post it as a full answer. – Salicylate

Presumably you also want each person to have as many roles as possible and not leave anyone without a role? So does this become an optimization problem? – Quinate

@IanMercer Edited to make it clear that each person should be assigned an equivalent number of roles. Also yes -- you can formulate the problem that way with a bipartate graph. The reason the formulation given in the question as poised is correct is as follows: – Henkel

Each node in the graph is a character, each edge in the graph represents two characters who share no scenes with each other. Each element of S is an assignment of a set of roles to a single person. – Henkel

@Rabush I think you've misunderstood. Every element of S is a complete subgraph in G (a clique). So, all the vertices within any element of S must share an edge with every other vertex in that element. The more connected G is, the easier this problem is to solve. – Henkel

@Henkel Thanks for the clarification, it would be worth putting the explanations back in the question rather than in the comments for anyone else who comes along. (FYI) – Quinate

Answer 1

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.

Unsocial

In the question I meant for edges to denote characters who share no scenes with each other. However, formulating the problem with the edges meaning the opposite and solving it with graph coloring is equivalent -- as you said. Ideally, there would be an equivalent number of nodes of each color. – Henkel