Dtyjlui

I have been working on this for a few days, brushing up on graph theory and disjoint sets, but I have not yet found an algorithm that is guaranteed to produce the optimal result and runs in better than $O(n^2)$ time.

The problem is to divide a tree graph, which is a connected undirected graph with no cycles, into 3 equal parts. More formally, given a tree graph $G$ with $n$ vertices, find the most even partition of $G$ into $3$ components $A, B, C$ with $a, b, c$ vertices, respectively. For this problem, "most even" is defined as having the largest value of $abc$ possible for the given graph $G$.

What I am most interested in learning is if there are properties of tree graphs I can leverage into proving that a trisection is the best (most even) possible without (in pathological cases) having to try all possible trisections. For example, if the most even bisection is so lopsided that the smaller "half" has fewer than $n/3$ vertices, I'm almost sure that means the most even trisection will be achieved by most evenly bisecting one of the 2 halves. But I have not been able to prove it yet.

I'm going to call vertices "nodes" from here on because it is a shorter word.

It is easy to cut the graph optimally in half in $O(n)$ time. Every edge has $x$ nodes on one side and $(n-x)$ on the other. Because there is only one path from any node to any other, you can compute these values for every edge in $O(n)$ time, and while you are calculating that, you can just keep track of which edge has the closest to $n over 2$ nodes on one side of it. Because you have checked every edge, you know this is the best you can do, even if $x ll frac n2$. It might not be the only edge that produces those size partitions, but that is not a concern.

So far, however, I have not found a way to prove that a given pair of edges are the best choice to cut to partition non-trivial $G$ unless either (a) the result is perfect, or (b) I compare it to essentially every other combination of 2 edges. I do not really have to compare every combination all the time, often I can cut the search space down, but I have not figured out how to prove that I have found the best possible partition in less that $O(n^2)$ time.

Everything I have come up with so far fails for various kinds of edge cases. The simplest case is a star tree, $n$ nodes all connected to one central node of degree $n$. If all I am doing is naïvely comparing edges and cuts, I have to try all possible combinations.

I can rank the edges, like I did with bisecting the graph, except this time rank them on how close the are to having $n over 3$ nodes on one side, but what if I have a tree like this:

$H$ is connected to 5 leaves and there are a total of 12 nodes in $G$. The edge closest to having $frac n3 = 4$ nodes on one side is the edge between $4$ and $5$, $(4,5)$, which splits $G$ into sets of 4 and 8 nodes. If I cut that edge, the next best edges to cut (if I am only looking at edges of $G$, and going by the ranking in the previous paragraph) are $(3,4)$ or $(5,6)$, but would result in partitions of ${8,1,3}$ and ${7,1,4}$ respectively. It will be a long time before I find the optimal solution of ${6,3,3}$.

Looking at this, I considered finding the best $frac 23$ cut and then cutting the larger set in half. Except for this graph, the best $frac 23$ cut is the same as the best $frac 13$ cut, so we would cut edges $(4,5)$ and $(H,6)$ giving us a ${6,2,4}$ partition.

Since bisecting the graph is easy, I looked at recursively bisecting the graph. I could build up a balanced binary tree of subgraphs, but I don't know what that would get me for a star graph or various kinds of lopsided graphs I can come up with. It might work to find an approximate answer, but I want to be sure I have the exact best answer.

The real graphs I am dealing with can be huge, up to $1,000,000$ vertices, so the $O(n^2)$ solution is not practical. The only real constraint I can rely on is that the diameter of the graph will not get out of control huge like that.

I am looking for either help finding the best edges to cut or help verifying that the partition I have found is the best possible for the given graph (or, of course, both.) Thanks.

I believe you can use Heavy Light Decomposition to get an $mathcal{O}(nlog^2n)$ time algorithm. This is quite complicated, so I will not bother with too many details. The idea is as follows.

Fix some root and determine the HLD. Then for every node we consider the subtree rooted at that node. We will call such subtrees rooted subtrees. We can easily do a linear time DFS to determine for every rooted subtree how many nodes it contains. Less obvious is that we can then do an $mathcal{O}(nlog^2n)$ time DFS on all heavy chains to determine for each rooted subtree the optimal $2$-cut of that subgraph. With all this information processed, we can find the optimal $3$-cut of the original graph in $mathcal{O}(nlog^2n)$ time.

The DFS on the heavy chains works as follows. For each chain, we work from bottom to top. We can keep track of all the sizes of rooted subtrees below the current node in a BST. So for each node $N$ in the heavy chain, from bottom to top, we add all sizes of rooted subtrees of its descendants not already in the BST (these can easily be found in linear time with a DFS), and then do a query to find the size closest to $s/2$ where $s$ is the size of the rooted subtree of $N$. Since each path from a root to a node intersects $mathcal{O}(log n)$ heavy chains, every node is only considered $mathcal{O}(log n)$ times. There are $n$ such nodes and BST operations cost $mathcal{O}(log n)$ time, so this step takes $mathcal{O}(nlog^2n)$ time in total.

Finally, finding the optimal $3$-cut of the original graph in linear time is still quite tedious. Any $3$-cut is itself a tree graph, when we connect two components if they are connected in the original graph. Notice there is only one possible tree graph with $3$ nodes. The root of our original graph will be in one component. We can consider two cases. The root component is connected to both other components, or only one.

If the root component is connected to only one other component, we can simply consider every possible rooted subtree and their optimal $2$-cut. Then you will find the optimal $3$-cut where the root component is connected to only one other component. This takes linear time.

If the root component is connected to both other components, things get a lot more complicated, and we will need to use our HLD again. We need a global BST for this step. It initially contains all sizes of rooted subtrees. For each heavy chain, we work from bottom to top. We want to consider for every node in the chain the optimal $3$-cut where one of the components is its rooted subtree. This means the other component that does not contain the root must be a disjoint rooted subtree. So we want to keep track of all such rooted subtrees in our BST.

If we traverse the heavy chains in a DFS, we can ensure that every rooted subtree containing the current heavy chain is already removed from the BST. Then, working from bottom to top, we can ensure that every rooted subtree below the current node is also removed from the BST. We can then do a $mathcal{O}(log n)$ BST query to find the optimal $3$-cut per node. Finally, we add all the rooted subtrees back to the BST. By similar analysis to before, this step will take $mathcal{O}(nlog^2n)$ time in total.