# Algorithm to find (edit?) distance from a partition into complete graphs

While I am aware of this thread and others like it: https://stackoverflow.com/questions/16399597/edit-distance-between-two-graphs, I am wondering if the following has been considered and in what parlance, if any. I have searched Archiv and Google, but my search-fu is weak, not normally working in this space.

Let $P$ be a partition of $n$ vertices, and within each element of $P$ (a subset of vertices), form a complete graph. The resulting graph $G_P$ is then composed of a union of complete graphs which are mutually disjoint. Given another (arbitrary) graph $H$ on $n$ vertices, I am interested in finding the set of such $P$ (not necessarily unique) that minimize the edit distance between $H$ and $G_P$.

While I can think of an algorithm to brute force this (but NP: take all partitions of $n$ vertices, and compare them one at a time to $H$--this is NP because the number of partitions is a Bell number ($O(e^{e^x}))$, I am wondering if there are any nicer (non-NP would be fantastic) formulations that exist, given the restriction to partitions into complete graphs.

finding the set of such $P$ (not necessarily unique)
Just a remark, not an answer. For $H$ a $4$-cycle, there are three partitions edit-distance $2$ from $H$:
So if $G$ is composed of $k$ disjoint copies of $H$, there are $3^k$ equally minimal partitions. So the cardinality of the set you seek can be exponential in the number of vertices.
• Thanks for the observation; so if the list is possibly exponential to write down, a sub-exponential (or polynomial)-type algorithm would be descriptive or heuristic in its determination of a list of acceptable $P$. – Steve Aug 25 '16 at 16:57