9
$\begingroup$

I'm working on trying to partition a triangulated graph into connected subgraphs with some guarantees on the number of inter-partition edges. Here's an example of a triangulated graph that has been partitioned into 4 "clusters": Example Triangulation with Partitioning

What I wanted originally was an algorithm that could create partitions of approximately k triangles (there could be some error as long it wasn't too large), and I managed to figure out a $O(k^2p^2(v+e))$ algorithm (where p is the total number of partitions) that could find such a partitioning. I then realized that having large numbers of inter-partition edges were detrimental for the application I needed this algorithm for.

Ideally, I'd like an algorithm that can keep each partition within some range of $k$, ideally have it be a constant factor like 2. Also, I'd like to be able to make the number of inter-edges have an upper bound that is "low".

Additionally, another problem I have is if I have a partition that has these properties, and I modify the graph by doing one of the following:

  • Adding a set of edges connecting to existing vertices
  • Adding a vertex and a set of edges connecting to the added vertex
  • Removing a set of edges
  • Removing a vertex and all edges that connect to this vertex

I want to be able to repartition the graph and still have each partition with size $k$ and number of cut edges minimized. (This is the solution I'm putting up a bounty for). This means that using this algorithm, we can construct any partition by starting with an empty graph and adding vertices and edges one by one and repartitioning.

Here's some additional constraints to the problem:

  • The graph is planar
  • Each "triangle" is a vertex that has undirected edges to triangles it shares an edge with
  • From the above statement, it is obvious that each vertex in this graph has degree at most 3
  • The graph is connected
  • Each subgraph from the partition is connected
  • Each subgraph has approximately k vertices
  • There are at most $\sqrt n$ inter-partition edges (edges that contain a vertices from different partitions). If you can find a similar bound for inter-partition edges like $2\sqrt n$ or $O(\log n)$ then that could work too. I'm not entirely sure the upper bound for inter-partition edges can be less than $O(n)$ so if you can prove that its impossible to do better, that is satisfying as well.

I'm at a point where I'm stuck, so any help with this problem would be lovely. If you can flat out solve this problem, you're the bees knees. Otherwise, if you know of any papers or textbooks or algorithms you could point me to, I'd appreciate it very much.

Let me know if I need to clarify anything!

EDIT: Here are some additional constraints if it makes the problem easier.

  • We are dealing with constrained delaunay triangulations
  • Constraints will NEVER be a single vertex
  • The graph created from the triangulation is constructed as follows: each triangle is represented as a vertex. Each edge in the graph corresponds to an unconstrained edge in the triangulation. This means that a constrained edge between two triangles will not show up in the graph representation of the triangulation.

Another thing I realized is that we may need to modify $k$ to grow as $n$ grows, otherwise there can be no sub $O(n)$ guarantees on the number of inter-partition edges.

Improve this question
$\endgroup$
8
  • 2
    $\begingroup$ It's not entirely clear what you want. Do you want a partition where each set is of roughly equal size, or one with a fixed number of sets ? I understand that in either case, you want to minimize the number of inter-set edges. $\endgroup$
    – Suresh Venkat
    Commented Feb 17, 2014 at 7:41
  • $\begingroup$ We only want the partitions to be sets of roughly equal size and within some range of k, we don't care about the total number of sets. $\endgroup$
    – zaloo
    Commented Feb 17, 2014 at 17:04
  • $\begingroup$ I see. so each partition should have roughly $k$ elements in it. $\endgroup$
    – Suresh Venkat
    Commented Feb 17, 2014 at 20:25
  • $\begingroup$ I don't have a guarantee for this heuristic, but since your graph is planar, something like a Miller hierarchy of rings might do the trick. In brief, use the planar separator theorem to split the graph into two roughly equal parts with a small number of edges between them, and recurse till all pieces are roughly of size $k$. You'll end up with a cut size close to $\sqrt{n}$. $\endgroup$
    – Suresh Venkat
    Commented Feb 18, 2014 at 6:42
  • $\begingroup$ Doesn't a planar separator not guarantee anything about the connectedness of the sets of vertices that are formed? $\endgroup$
    – zaloo
    Commented Feb 18, 2014 at 17:12

4 Answers 4

Reset to default
11
+100
$\begingroup$

Rao has two papers on sparsest cut in planar graphs, a constant-factor approximation in quasi-linear time seems possible. Recursive bisection, while not ideal, might be a feasible approach for your problem.

Satish Rao. Finding near optimal separators in planar graphs. In 28th Symposium on Foundations of Computer Science (FOCS), pages 225-237, 1987.

Satish Rao. Faster algorithms for finding small edge cuts in planar graphs (extended abstract). In 24th ACM Symposium on Theory of Computing (STOC), pages 229-240, 1992.

Horst D. Simon and Shang-Hua Teng. How Good is Recursive Bisection? In SIAM Journal on Scientific Computing, Volume 18, Issue 5, pages 1436-1445, 1997.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Awesome links, I'll check them out! $\endgroup$
    – zaloo
    Commented Feb 23, 2014 at 1:11
8
$\begingroup$

http://cse.iitkgp.ac.in/~pabitra/paper/barna-sdm07.pdf

BAM, here's the answer. Incremental min cut graph partitions in $O(k^3)$ time for insertions and deletions. If you make $k = O(\log n)$ then it's poly logarithmic for insertions and deletions, which is damn good.

Improve this answer
$\endgroup$
2
  • $\begingroup$ there were many constraints given on the problem. does this really satisfy all of them? $\endgroup$
    – vzn
    Commented Feb 24, 2014 at 0:42
  • $\begingroup$ Yes. We can choose any size k for any step. We guarantee minimized cut-edges (inter-partition edges). We also have the ability to add and remove vertices and edges in low time complexity. That satisfies everything. $\endgroup$
    – zaloo
    Commented Feb 24, 2014 at 1:24
2
$\begingroup$

The following algorithm might help.

1. Choose any vertex from the graph.

2. Do a BFS untill $O(K)$ vertices has been visited.

3. Create a cluster with the visited vertices. (Connectivity is ensured for the cluster).

4. Remover the visited vertices from the graph.

5. Repeat 1-4 untill all nodes are visited.

Every cluster contains $O(K)$ vertices and those vertices are found by BFS. Again the the degree of each vertex is constant. So the inter-cluster edges are also $O(K)$. I think it's a lower bound on the number of inter-cluster edges. The complexity of the algorithm is clearly linear in number of edges as only BFS is performed. The number of cluster is also $O(N/K)$.

Also modification of the graph by adding vertices would not affect the partition. Any one partition in which one of the neighbour of the new vertex lies, that can be the partition of the new vertex. So , may be no repartition is required untill the size of one of the cluster becomes too much.

Edit:

Here is a proof that it is not possible to do better than linear number of inter-partition edge for arbitary $k$. Let in some partition there are $m$ vertices and it is connected. At best, the corresponding triangles would construct a convex region $\mathscr{R}$. Now for arbitary $k$ the convex hull of $\mathscr{R}$ can contain $O(K)$ triangle corners. So in total you would have $O(K)$ edge going out from $\mathscr{R}$. However if $k$ is $O(log n)$ then may be the inter-partition edges can be reduced.

Improve this answer
$\endgroup$
10
  • $\begingroup$ 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)$"? $\endgroup$
    – András Salamon
    Commented Feb 20, 2014 at 16:20
  • $\begingroup$ 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. $\endgroup$
    – Suresh Venkat
    Commented Feb 20, 2014 at 16:43
  • $\begingroup$ 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 $\endgroup$
    – Dibyayan
    Commented Feb 20, 2014 at 17:07
  • $\begingroup$ Because of the above the inter-cluster edges is $O(K)$. @AndrásSalamon $\endgroup$
    – Dibyayan
    Commented Feb 20, 2014 at 17:08
  • $\begingroup$ Ah you mean in the dual graph ? not the primal planar graph. $\endgroup$
    – Suresh Venkat
    Commented Feb 20, 2014 at 17:18
-1
$\begingroup$

did some search on this but held off on posting immed to see what other answers would materialize & am now posting this to not throw away some misc ideas/leads which could have some value (although the question author has already indicated hes now found an acceptable answer).

on inspection there are many constraints given on this problem and it could conceivably take an entire paper to create an algorithm & prove that it satisfies all them (which of course is generally outside the scope of stackexchange format). nevertheless there are a few basic approaches to take on this type of problem

  1. empirical. generate random graphs that fit the constraints or use graphs from some dataset that match the conditions and try different algorithms on them, and look at performance. one may find that an algorithm empirically satisfies the conditions reqd. if one is more strict, one could attempt to create a proof out of the empirical observation if its 100% satisfied by large datasets. also for empirical research it often helps to know how the datasets are obtained/generated, what their nature/origination is.

  2. the question has no related citations of literature/refs. so what are the nearest types of algorithms in the literature? for this type of problem multiple types of research areas might overlap. there is research on planar graphs, graph partitions, graph cuts, graph separators, partitioning triangular graphs, etc.; its not obvious to figure out the main theme of this question so far as its formulated or which particular (graph algorithm) research sub-area would most directly impinge on it.

given those qualifications a basic theme of the question seems to be "partitioning planar graphs". here are some leading recent refs on that topic which might be helpful & show additional themes/angles of current related research. there are some algorithms implemented & they may be available on request from the authors.

the 3rd involves partitioning with weights, which will generalize to equal weights, but which gives an additional framework for consideration/investigation: could all the question conditions be fulfilled by some kind of weight assignment scheme? (this could also tie in with the requirement to have some kind of dynamic control or adjustment over solutions also referred to in the question.)

Improve this answer
$\endgroup$

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.