Timeline for Partitioning graphs while minimizing inter-partition edges
Current License: CC BY-SA 3.0
14 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 20, 2014 at 21:29 | comment | added | zaloo | I understand exactly what you're saying. I believe that I'll need to have the size of $k$ to be related to $n$. I modified my OP to reflect this and to have some additional constraints as well, so I hope that helps. | |
| Feb 20, 2014 at 18:43 | history | edited | Dibyayan | CC BY-SA 3.0 |
added 5 characters in body
|
| Feb 20, 2014 at 18:38 | comment | added | Dibyayan | Not sure if the edit is notified to the author of the question. So, may be there is a proof for showing that $O(N)$ edges is unavoidable.Please see in the edit. @zaloo | |
| Feb 20, 2014 at 18:34 | history | edited | Dibyayan | CC BY-SA 3.0 |
Proof of lower bound on number of inter-partition edge for arbitary $k$
|
| Feb 20, 2014 at 18:11 | history | edited | Dibyayan | CC BY-SA 3.0 |
deleted 5 characters in body
|
| Feb 20, 2014 at 18:09 | comment | added | Dibyayan | I think in that case you need a nicer defination for the value of $k$. Some arbitary value of $k$ certainly won't work. In planar graphs number of edges is linear in number of vertices. With proper denser partition and setting the value of $k$ appropriately we may get constant number of inter partition edges. Certainly, i shall think about it. | |
| Feb 20, 2014 at 17:29 | comment | added | zaloo | There might be even more degenerate cases when each each partition has the form of a tree where the root node has 3 children and the rest have 2 children. In this case there are (k-1)/2 leaves that each have 2 inter partition edges. That means we have k-1 interpartition edges for each partition, which for a graph of vertices with degree 3 gives us $(n/k)(k-1) = n-1/k$ inter-partition edges. This is only a reduction of 1/3rd of the edges which isn't very nice. However I'm not even sure if there is a way to have less than O(n) inter-partition edges so I might be being too picky. | |
| Feb 20, 2014 at 17:22 | comment | added | zaloo | This algorithm is almost identical to the $O(k^2p^2(v+e)) $ algorithm that I had initially developed. The problem with this is that you can still have O(n) inter-partition edges which is undesirable. If every vertex in the graph has degree 3 and you imagine taking "lines" of vertices as partitions (where each vertex in the partition has only degree 1 or 2), then there are guaranteed to be $n/3$ inter-partition edges. | |
| Feb 20, 2014 at 17:18 | comment | added | Suresh Venkat | Ah you mean in the dual graph ? not the primal planar graph. | |
| Feb 20, 2014 at 17:08 | comment | added | Dibyayan | Because of the above the inter-cluster edges is $O(K)$. @AndrásSalamon | |
| Feb 20, 2014 at 17:07 | comment | added | Dibyayan | The degree of each vertex in the graph is at most 3. It is less than 3 if it is on the boundary and no outerface is considered. Hence each vertex has constant degree. @SureshVenkat | |
| Feb 20, 2014 at 16:43 | comment | added | Suresh Venkat | I think the answer refers to planar graphs. But I still don't see why "each vertex has constant degree" ? this is true "on average" but not for any vertex. | |
| Feb 20, 2014 at 16:20 | comment | added | András Salamon | If you apply this to a complete graph, then there are $\Omega(N(N-K))$ inter-partition edges. Why do you say "the inter-cluster edges are only $O(K)$"? | |
| Feb 20, 2014 at 16:05 | history | answered | Dibyayan | CC BY-SA 3.0 |