1
$\begingroup$

Let $G=(V,E)$ be a complete finite graph with the vertices arranged in a circle. Each edge has a nonnegative weight, and we would like to find an efficient algorithm to find a subgraph of maximum total weight, which is a triangulation of the graph. A triangulation of the graph is a subgraph such that no edges cross and no edge can be added to the graph without adding a crossing edge.

Of course as you go around the circle every edge will be added since the weight is nonnegative and these edges can never cause a crossing.

I initially thought of a greedy algorithm, selecting the highest weight edges and eliminating all crossing edges, but of course that won't work. I also thought about eliminating least weight edges but it seems to me that would probably also not work for the same reason.

I also tried to think of a divide-and-conquer algorithm, perhaps sped up by dynamic programming or something. My only thought was to first pick a random vertex and then iterate through all edges, finding the maximum graph weight if the edge were included (by first finding the maximum weight triangulation on one side of the edge and then on the other). But the runtime then seems like it has the equation

$$ T(n)=[T(n-1)]+[T(4)+T(n-2)] + ... + [T(n-2)+T(4)]+[T(n-1)] $$

and that doesn't seem like it would be efficient.

$\endgroup$

1 Answer 1

2
$\begingroup$

With proper classification and memoization, an approach by dynamic programming runs in $O(n^3)$ time, where $n=|V|$. That seems efficient enough considering there are $n(n-1)/2$ edges.


Assume $n\ge 3 $; otherwise it is easy to solve the problem.

Label the vertices be $v_0, v_1, \cdots, v_{n-1}$ clockwise. Let $v_n=v_0$.

For $0\le i<j \le n$ and $v_i\neq v_j$, define $OPT[i][j]$ as the maximum weight of a triangulation of the subgraph induced by vertices $v_i, v_{i+1}, \cdots, v_j$ that contains the edge between $v_i$ and $v_j$. We have

$$OPT[i][i+1]=\text{weight}(v_i, v_{i+1}).$$

Split by vertex v_k. Image made by Microsoft Paint

$$OPT[i][j]=\text{weight}(v_i, v_j) + \max_{i\lt k\lt j} \left\{ OPT[i][k] + OPT[k][j] \right\},\quad\text{if } j\ge i+2.$$

A triangulation of $G$ must contain an edge between $v_0$ and $v_i$ for some $0\lt i\lt n$. Hence the maximum weight of a triangulation is $$\max_{0<i\lt n} \left\{ OPT[0][i] + OPT[i][n] - \text{weight}(v_0, v_i)\right\}.$$

It takes $O(n)$ time to compute an entry of $OPT$. There are $O(n^2)$ entries to compute. The overall complexity is thus $O(n^3)$.

With more bookkeeping, the triangulation of the maximum weight can be found without increasing the time-complexity.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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