Seeking a Polynomial Time Algorithm for Balanced Weight Assignment to Nodes in a Tree

Question

I have a tree, $T$, with $n$ nodes. My goal is to assign a non-zero weight to each node such that the following condition is met:

Upon removing any arbitrary node, the total weight of nodes in each resulting connected component should be equal.

Consider the following tree as an example:

1 -- 2 -- -3 -- 4
     |
     1

In this tree, if we remove any node, the total weight of the nodes in each of the resulting connected components is equal. For instance, if we remove the node with weight $-3$, we end up with two connected components, each with a total weight of $4$.

I am seeking an algorithm that can find these weights in polynomial time.

My initial approach was to assign arbitrary values to the nodes. Then, for each node, I would check if the condition is satisfied when that node is removed. This check can be performed in $O(n)$ time using graph traversal algorithms like BFS or DFS. However, I am unsure how to adjust the tree because correcting the condition for one node seems to disrupt the condition for almost all other nodes.

Any suggestions or insights would be greatly appreciated.

Answer 1

Using the idea of @Mahyar, I think there is another way to find a solution to the problem.

Given a tree $T= (V, E)$, find a bipartition of $T = (X\sqcup Y, E)$ (using a simple graph traversal). Consider the following weighting function:

$$w : \begin{array}[t]{rcl} V & \to & \mathbb{Z}\\ v & \mapsto & \left\{\begin{array}{ll} \deg(v) & \text{if }v\in X\\-\deg(v)&\text{if }v\in Y\end{array}\right. \end{array}$$

Then it satisfies the property.

Indeed, when deleting a vertex of $X$, the resulting connected components are of weight $-1$. When deleting a vertex of $Y$, the resulting connected components are of weight $1$. The total weight of the tree is $0$.

Proof:

• $w(T) = 0$. Indeed, $w(T) = \sum\limits_{x\in X}\deg(x) - \sum\limits_{y\in Y}\deg(y) = 0$, because the graph is bipartite.
• Deleting a node of $X$ (resp. $Y$) creates connected components of weight $-1$ (resp. $1$). The idea of the proof is basically the same as in @Mahyar's answer: we consider $r\in V$ an arbitrary root. For $v\in V$, we note $h(v)$ the maximal distance from $v$ to a leaf of the tree $T$ rooted in $r$. We prove by induction on $h(v)$ that the result is true.

  • if $h(v) = 0$, $v$ is a leaf, hence of weight $1$ or $-1$. Deleting $v$ creates one connected component of weight $-w(v)$, because $w(T) = 0$;

  • suppose the result true for all $v$ such that $h(v) \leqslant k$, for some $k\geqslant 0$. Let $x\in X\setminus \{r\}$ (the case $Y$ is similar) such that $h(x) = k + 1$. In the tree $T$ rooted in $r$, all children of $x$, $v_1, v_2, …, v_{d-1}$, with $d = \deg(x)$, verify $h(v_i) \leqslant k$. Let $T_i$ be the subtree rooted in $v_i$.

    Since each $v_i\in Y$, using induction hypothesis, for all $i$, $w(T\setminus T_i) = 1$. That means that $w(T_i) = w(T) - w(T\setminus T_i) = -1$. Now, the connected components created by the deletion of $x$ are the $T_i$'s, and the rest of the tree: $T\setminus (\{x\}\cup T_1 \cup… \cup T_{d-1})$. The weight of this connected component is: $$w(T) - w(x) - w(T_1) - … - w(T_{d-1}) = -1$$

  • the case of the root is similar, just without this last connected component.

Answer 2

We can weight vertices such that the entire tree has a fixed sum of weights; for example, zero.

Let us design a recursive procedure that assigns weights to the vertices of a tree $T$ with root $r$ such that the weight of $T$ is zero, and after removing $r$ from $T$, weight of every remaining component is $S$. We call this procedure $\texttt{root}(r, S)$.

$\texttt{root}(r, S)$ assigns to $r$ a weight of $- S \times \deg(r)$, as weight of $T$ should be zero. We already know that for each child $v$ of $r$, weight of the subtree with root $v$ is $S$. We want to make sure that, when $v$ is removed, every remaining component has the same weight. One such component consists of $r$ and subtrees of children of $r$ except $v$. This component has weight $S' = - S \times \deg(r) + S \times (\deg(r) - 1) = -S$. So, every other component after removing $v$ should also have weight $S'$; if $v$ is not already weighted, a call to $\texttt{root}(v, S')$ will weight vertices in subtree of $v$.

We pick an arbitrary root $r$ and a non-zero $S$, and call $\texttt{root}(r, S)$ in a top-down style. This algorithm runs in time $O(n)$.

Answer 3

All the solutions for $w$ the weight function on the (vertices of the) tree $T=(V, E)$ can be obtained combining Mahyar's and Nathaniel´s answers in this way:

1. Pick any arbitrary numbers $S$ and $S'$.
2. For a bipartition $T = (X\sqcup Y, E)$, assign $S$ to all vertices in $X$, and $S'$ to all vertices in $Y$. This will be the sum of the weights of vertices in each connected component resulting from removing the given vertex.
3. Assign weights $w(x) = S + S' - deg(x) \cdot S$ to vertices $x \in X$, and $w(y) = S + S' - deg(y) \cdot S'$ to vertices $y \in Y$.

This modifies procedure $\texttt{root}(r, S)$ to assign weight $w(r)$. You can see how $\texttt{root}(r, S)$ causes alternating $S$ and $S'$ as it recurses. And the sum of all weights in the tree $T$ is $w(T) = S + S'$ (not necessarily 0).

In Mahyar's answer $S' = -S$, while in Nathaniel´s answer $S = 1$ and $S' = -1$.

For proofs, it is useful to show that, for any tree T holding OP's propery,

• $w(T) = w(v) + deg(v) \cdot S(v)$ for all $v \in V$,
• $w(T) = S(u) + S(v)$ for all adjacent vertices $u,v \in V$.