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.

  • $\begingroup$ 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$. $\endgroup$ – Steve Aug 25 '16 at 16:57

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.