I am looking for algorithm which allows to do following:
Let $T$ is some tree, where each vertex $V_i$ has its cost $c_i$. I am looking for algorithm which allows to split $T$ (by removing two edges) to three connected components $S_i$ with equal sum of costs of vertices
$\endgroup$ 52 Answers
$\begingroup$Wouldn't something like this base algorithm work?
- Collect all leafs
- For all nodes connected with a leaf, create a new leaf with the sum of the leafs and the node.
- Once it exceeds 1/3 of the total, cut it off as a tree.
There will be special cases, and you may need to throw in some tree balancing when there are large differences in weights of the leafs/nodes.
$\endgroup$ 3 $\begingroup$What I would have done is to do a DFS of the tree and for each node calculate the sum of the cost of the node and it's descendents. One stores the path to the nodes along with this values and then sorts by value.
Then one can identify which nodes that carry about a third of the cost and spawn that one off. Then for the second to be spawned of you need to take into account whether the first node is a descendent or not (which is where the stored path would be used). If the first is a descendent the second would have to carry about two-third of the cost, otherwise it would have to carry one-third (you have to look for this second at two places in the sorted list).
This should have $O(N\log N)$ time complexity and $O(N)$ space. If the tree is very deep you would need to use a hash-table representation of the path or the depth would have an impact on the complexity. Also there would be some cost if there's many candidates for the first and second nodes that have to be considered (if it's critical that the solution is optimal).
To take an example, consider the sexp (1 (2 (3 (4 5) 6) 7 8 (9 (10 11) 12))) (the parenthesis following a number contains it's children, the tree is that from wikipedia on DFS). Doing the DFS search (which is right to left for a sexp) gives a table of costs:
$$\begin{matrix} \text{path} & \text{cost}\\ \hline 1/2/3/4 & 4\\ 1/2/3/5 & 5\\ 1/2/3 & 12\\ 1/2/6 & 6 \\ 1/2 & 20 \\ 1/7 & 7 \\ 1/8/9/10 & 10 \\ 1/8/9/11 & 11 \\ 1/8/9 & 30 \\ 1/8/12 & 12 \\ 1/8 & 50 \\ 1 & 78 \end{matrix}$$
Then you sort by cost:$$\begin{matrix} \text{path} & \text{cost}\\ \hline 1/2/3/4 & 4\\ 1/2/3/5 & 5\\ 1/2/6 & 6 \\ 1/7 & 7 \\ 1/8/9/10 & 10 \\ 1/8/9/11 & 11 \\ 1/2/3 & 12\\ 1/8/12 & 12 \\ 1/2 & 20 \\ 1/8/9 & 30 \\ 1/8 & 50 \\ 1 & 78 \\ \end{matrix}$$
Now you're looking for a cost of $78/3 = 26$, the best match is $1/2$ and the second best is $1/8/9$. Now you see that they and their descendents are disjoint so they're allowed. We should also for the second consider matches near $2\times78/3=52$, for example $1/8$ we see on the path that the node $1/8/9$ and it's descendant is subtree of $1/8$ and it's descendants (which is the case that would include $1/8$. So now we have two candidates, using the subtrees rooted by $1/8/9$ (of cost $30$) and $1/2$ (of cost $20$) and the remainder (of cost $28 = 70-30-20$). The other candidate is the subtree rooted by $1/8/9$ (of cost $30$) and $1/8$ (of cost $20=50-30$) and finally the remainder (of cost $28 = 78-50$). This last step differs a bit depending how you value the goodness of the solution, here I'd say they're equally good, you divide both with costs $20+28+30$.
A comment was that the algorithm seem to require a directed tree, but that can be created selecting a root node. As an example if we use the same (undirected) tree and choose $4$ as the root instead we get the table:
$$\begin{matrix} \text{path} & \text{cost}\\ \hline 4/3/2/1/8/12 & 12 \\ 4/3/2/1/8/9/11 & 11 \\ 4/3/2/1/8/9/10 & 10 \\ 4/3/2/1/8/9 & 30 \\ 4/3/2/1/8 & 50 \\ 4/3/2/1/7 & 7 \\ 4/3/2/1 & 58 \\ 4/3/2/6 & 6 \\ 4/3/2 & 66 \\ 4/3/5 & 5 \\ 4/3 & 74 \\ 4 & 78 \\ \end{matrix}$$
You see here for example that the nearest to $26$ is $4/3/2/1/8/9$ with cost $30$. And in looking near $52$ we see $4/3/2/1/8$ with cost $50$ and $4/3/2/1$ with cost $58$, both of these are antecedents of the first so they are allowed. These exactly corresponds to the solution in the first case (ie you cut between $8$ and $9$ in combination with $1$ and $2$ or $1$ and $8$).
$\endgroup$ 6
