Is there a reasonable algorithm to generate a certain "independent clique graph" with minimal vertices?

Question

In the process of trying to find a solution to the rat and poison puzzle with two rats, I've found myself needing the solve the following problem, in polynomial time:

Given any $k_0, k_1, k_2,..., k_{n-1} \in [2,\infty)$, we want to produce a simple graph $G = (V, E)$ and some $c_0, c_1, c_2,..., c_{n-1} \subseteq V$ such that:

• Each set of vertices $c_i$ is a clique of size $k_i$ in $G$
• For all $(u, v) \in E$, there exists exactly one $c_i$ such that $u, v \in c_i$
• $|V|$ is minimal.

This essentially means that we want a graph with at least $n$ cliques, each of size $k_i$, such that each edge is in exactly one of these cliques, and we want the smallest such graph. Extra cliques that aren't represented by a $c_i$ will still occur but don't count as overlap, so $G$ isn't generally a block graph.

Answer 1

My initial thought was the following framework for an algorithm:

let c = empty array of size n
let G = ({}, {})
for i in [0, n):
    while there's not an independent set of size k_i in G:
        add a new vertex to G
    let S = an independent set of size k_i in G:
    connect every vertex in S to every other vertex in S in G
    let c[i] = S

The glaring issue is that I'm relying on a algorithm for independent set here, and there's no general polynomial-time algorithm for it. What I'm trying to figure out is if there is some structure inherent to this problem that makes independent set feasible to compute.

There's a polynomial time algorithm for finding an independent set on a chordal graph (though I can't find a straightforward presentation of the algorithm anywhere yet), so if I can prove that $G$ is always a chordal graph I've solved the problem.

A graph is chordal iff it has a perfect elimination ordering, an ordering of the vertices such that for any vertex v, v and the neighbors of v that occur later in the ordering form a clique. I'll prove this using induction.

Base case: Our starting graph has a trivial empty ordering, so our base case holds.

Inductive step: We need to show that adding some number of vertices, then filling out an independent set they are part of into a clique, creates a new graph with an ordering if the original graph already had one.

Let $s$ be the previous ordering (for example, $1342$). Let $t$ be an arbitrary ordering on the new vertices. Let our new ordering be $ts$, the concatenation of the two orderings. Since the only edges these new vertices have are within the new clique, and removing any of the vertices in a clique leaves the remaining vertices in a clique as well, as we move across $t$ and check if it forms a clique with the following neighbors in $ts$, it always will. Since we already know the vertices in $s$ satisfy the ordering criteria by the induction hypothesis, all the vertices in $ts$ satisfy the induction hypothesis and our new graph has a perfect elimination ordering. So the inductive step holds

So by our base case and inductive step, on every step of the algorithm, finding the independent set will take only polynomial time in the total number of nodes and edges, and since adding a $k_i$-clique can always be done in $k_i$ or fewer new vertices, the number of vertices is at most $\sum_{i=0}^{n-1} k_i$, the number of edges is at most the square of that, and therefore the whole algorithm is polynomial in the sum of the inputs, as desired.

I haven't proved that the result has the minimal number of vertices yet. That's going to have to wait for another day though. Might have to explain the previous parts a bit better too.