We have a graph with $N$ nodes and $N-1$ undirected edges, where it's possible to reach one node from any other node. Each node will get assigned a value randomly from [1,...,10]. We want the value of every node to end up at 10. The way we update is as follows, whenever we visit a node, we increment the value of that node by 1 with wraparound (e.g. 7 -> 8 and 10 -> 1). We can revisit nodes and edges as we please. We don't initially advance the counter in our node we start from. Return the number of possible nodes we can start from, such that every node ends with value 10.

I tried just doing simple backtracking search on the states, but the complexity is way too high, and I don't know when I can say "not possible", since we can cycle from 10 to 1.

  • $\begingroup$ Do you have a specific question about this task? $\endgroup$
    – D.W.
    Feb 25 '20 at 0:51
  • 1
    $\begingroup$ Are you thinking about trees? If the graph has a cycle, it wouldn't be connected. $\endgroup$
    – Daniel
    Feb 25 '20 at 16:18

Let $k$ be the value where we wrap around, in this case $10$. Then the problem can be solved in $\mathcal{O}(n^2 k^2)$ with DP. With some tricks we will improve this to $\mathcal{O}(n k^2 \log n)$. For fixed $k$ this complexity is nearly linear, $\mathcal{O}(n \log n)$. Both algorithms work even on worst-case inputs: the assumption of random assignment of values is unnecessary.

We start from the $\mathcal{O}(n^2 k^2)$ algorithm. A connected graph with $n$ vertices and $n-1$ edges is a tree. To check if we can start from some vertex $r$, root the tree at that vertex. We will store the dp states $DP[i][t]$, which will denote if the subtree of vertex $i$ can be made to contain only the value $k$, if we cross the edge between $i$ and its parent $t$ times $(\text{mod}\ 2k)$, and our path starts from an ancestor of $i$. After calculating the $DP$, we know that the path may begin from $r$ iff $DP[r][2k-1] = 1$.

Note that we may assume that all edges are traversed at least once, since traversing any path back and forth $k$ times changes nothing. Additionally, crossing some edge $2k$ more or less times doesn't change whether a solution exists as long as we still cross it at least once, as we can re-connect the tours visiting these vertices such that we get a path that visits every vertex the same amount of times $(\text{mod}\ k)$.

Let $C_{i, j}$ denote the $j$th child of vertex $i$. Let $V_i$ denote the number of times we have to visit the vertex $(\text{mod}\ k)$ for its value to equal $k$. We have the requrrences

\begin{gather} DP[i][2t_0] = \max_{\sum_{j} t_j = V_i\ (\text{mod}\ k)} \min_{j = 1, \dots, |C_i|}DP[C_{i, j}][2t_j]\\ DP[i][2t_0 - 1] = \max_{\sum_{j} t_j = V_i\ (\text{mod}\ k)} \max_{r = 0, \dots, |C_i|} \min_{j = 1, \dots, |C_i|}DP[C_{i, j}][2t_j + \mathbb{I}_{r}(j)] \end{gather} where $\mathbb{I}_{r}(j) = 1$ iff $r = j$.

The first recurrence holds, since if we cross the edge from $i$ to its parent $2t_0$ times and the edge from $i$ to its $j$th child $2t_j$ times, we visit $i$ exactly $\sum_j t_j$ times, which must equal $V_i\ (\text{mod}\ k)$. On the other hand, since the edges crossed an odd number of times form a path starting from $r$, and we cross the edge from $i$ to its parent an even number of times, we must likewise cross the edges from $i$ to its children an even number of times.

The second recurrence similarly holds, since if we cross the edge from $i$s parent to $i$ $2t_0 - 1$ times, $t_0$ of those crossings end in $i$, and if we cross the edge from $i$ to its $j$th child $2t_j + 1$ times, $t_j$ of those crossings end in $i$. Thus this sum must equal $V_i\ (\text{mod}\ k)$. The same path argument gives us that we may cross at most one edge from $i$ to its children an odd number of times.

These recurrences can be computed in $\mathcal{O}(|C_i| k^2)$ by initialising $DP[i][t] = \mathbb{I}_{0}(t)$, then looping over the children, at child $j$ assigning \begin{gather} DP[i][2t-1] \gets \max_{0 \leq t_1 < 2k} \max_{r = 0, 1} \min(DP[i][2t - 2t_1 - r],\ DP[C_{i, j}][2t_1 + (1 - r)])\\ DP[i][2t] \gets \max_{0 \leq t_1 < 2k} \min(DP[i][2t - 2t_1],\ DP[C_{i, j}][2t_1])\\ \end{gather} At this point, $DP[i][2t-r]$, for $r \in {0, 1}$, is one if we can visit $i$ in total $t$ times, crossing the edge from $i$s parent to $i$ exactly $-r$ times $(\text{mod}\ 2k)$, but we need the amount of visits to equal $V_i$, so we finally assign \begin{gather} DP[i][2t] \gets DP[i][2V_i - 2t]\\ DP[i][2t-1] \gets DP[i][2V_i - 2t - 1]\\ \end{gather}

The complexity of checking one $r$ is thus $\mathcal{O}(\sum_i |C_i| k^2) = \mathcal{O}(n k^2)$, giving the complexity $\mathcal{O}(n^2 k^2)$.

We can optimise this by noticing that we calculate the same $DP$ values multiple times. However, the straightforward approach of leveraging this fails: calculating $DP'[i][p][t]$, where $p$ is the neighbour of $i$ that is an ancestor of $i$ might take $\mathcal{O}(n^2 k^2)$ time, even though there are only $4(n-1)k$ states: consider the star graph. To fix this issue, we use centroid decomposition.

The centroid is a vertex of the tree, such that if we root the tree at that vertex, every subtree will have size at most $\frac{n}{2}$. Such a vertex always exists. Our algorithm will work as follows:

  1. Root the tree at the centroid $r$
  2. Calculate $DP'[C_{r,j}][i][t]$ for all $j, t$ in $\mathcal{O}(nk^{2})$. This gives us the answer for $r$
  3. Using these values, calculate $DP'[i][C_{r,j}][t]$ for all $j, t$ in $\mathcal{O}(|C_r| \log |C_r| k^2)$
  4. Disable vertex $r$ and recurse to the remaining subtrees. Whenever we try to visit vertex $r$, just return the already calculated $DP$ values.

Before addressing how to do step 3, we'll calculate the complexity of this approach. At the $m$th (0-indexed) round, the size of every remaining subtree is at most $n2^{-m}$. Thus there are at most $\log n$ rounds. During the $m$th round, every remaining subtree is adjacent to at most $m \leq \log n$ already handled vertices. If $n_r$ is the size of the remaining subtree $r$ is in when $r$ is picked centroid, then steps 1-3 for that subtree take $\mathcal{O}((n_i + \log n) k^2 + |C_r| \log |C_r| k^2)$ time (due to the already handled at most $\log n$ vertices).

Since there are at most $\log n$ rounds, and the sum of $n_r$ of $r$ participating in that round is at most $n$, we have $\sum_{i} n_i \leq n \log n$. Thus the total complexity is

\begin{equation} \mathcal{O}(\sum_{i} n_i k^2 + k^2 \log n + |C_i| \log |C_i| k^2) = \mathcal{O}(n k^2 \log n) \end{equation}

since each term sums to at most this.

It remains to show how to do step 3. Note that our approach to calculating $DP[i][t]$ doesn't care about the processing order of the children. Say $|C_r| = 2^{m}$. First, using our approach, calculate the intermediate values for children with index in $[1, 2^{m-1}]$ and in $[2^{m-1} + 1, 2^{m}]$. At the $s$th (1-indexed) step, using the previously calculated values, calculate the values for children with index not in $[x 2^{m-s} + 1, (x+1) 2^{m-s}]$, for all $x$, in $\mathcal{O}(2^{m-s} k^2)$ time per interval (by including the other $2^{m-s}$ indices not in this inteval but in the interval in the previous step containing this interval). After the last step, we get $DP'[C_{r, j}][r]$ from the intermediate value for all children but $C_{r, j}$. This is indeed $\mathcal{O}(|C_r| \log |C_r| k^2)$.


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.