3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

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$:

          EditDistance
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.

Improve this answer
$\endgroup$
1
  • $\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, 2016 at 16:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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