List Colouring Trees in Logarithmic Space

The Compositon complexity of majority

BGJ - List Colouring Trees in Logarithmic Space

Result

• List colouring can be solved on $n$ vertex trees by a deterministic machine using $O(\log n)$ work tape.

Setup

• Given a graph and a list of possible colors $L(v)$ for all $v$, is there a coloring such that $c(v)\in L(v)$ for all $v$ with $c(v_1)\neq c(v_2)$ if $(u,v)\in T$.
• List colouring is hard on planar bipartite graphs even if all lists are of size at most 3.
• $W[1]$ hard if parameterized by treewidth.
• Can be solved with linear space and linear time on trees with hashing.
• The description of the tree and the colors are on a read only tape which does not count for the space complexity.
• As trees have pathwidth $O(\log n)$, the problem can be solved non-deterministically in $O(\log^2 n)$ space.
• $T_v$ is the subtree rooted at $v$ and $T-v$ the forest resulting from deleting $v$.
• Traversing a tree can be done in $O(\log n)$ space. Same with count the number of vertices in a subtree, child with the maximum subtree size, enumerate children ordered by the subtree size.

Path Decompositions.

• A path decomposition is a tree decomposition that is a path.
• A nice path decomposition has empty bags on the endpoints of the path, and two consecutive bags differ only by at most one vertex.

Warmup

• List colouring can be solved non-deterministically using $O(\log n\log \Delta)$ space of trees with maximum degree $\Delta$.
  • This uses the following two lemmas
  • List colouring can be solved non-deterministically in $O(k\log \Delta + \log n)$ space if we can compute deterministically a path decomposition for $G$ with width $k$ in $O(\log n)$ space.
  • If $T$ is a tree, we can deterministically compute a path decomposition of width $O(\log n)$ using $O(\log n)$ space.
• We call a vertex heavy if its subtree has more vertices than any other of its siblings from the same parent.
• Now a way to do this would be Loop over possible colours of the root $v$ and then check if a colouring can be extended to all subtrees $T_v$ for $v$ being a child of the root while not giving the colour $c$ to the root.
  • Having for this a space bound of $S(n) = f(n)\log n$ gives us a recursive space of $S(n/2) \leq S(n)-f(n)$.
  • So when we recursive on a non-heavy child we are fine with some bits to spare.
    • Suppose now $v$ has non-heavy children $v_1,\dots,v_k$ and heavy child $u$.
    • Suppose the parent of $v$ needs to be assigned colour $c'$. Then one of the following must be true:
      • There is no colouring of $T_v-T_u$ which avoids colour $c'$ for $v$. This implies reject as it contradicts the edge of $parent(v)$ and $v$
      • There is a unique colour $c\neq c'$ that can be assigned to $v$ for a list colouring of $T_v-T_u$.
      • There are two possible colours unequal to $c'$ which can be given to $T_v-T_u$ and it can be coloured for the heavy child $T_v$.
• A deterministic algorithm using $O(\log^2 n)$ space and poly time.
  • Algorithm Solve(v,p) where $p$ denotes that $v$ cannot recieve the $p$th colour in $L(v)$ (0 mean no restriction):
    • Let the children of $v$ be $v_1,\dots,v_k$ and $u$ the heavy child.
    • Recursively verify that $v_i$ can be coloured by using Solve($v_i$,0). Reject if any rejects.
    • If $|L(v)| \geq k+2$ we free up our memory and verify that $T_u$ can be coloured by calling Solve($u$,0).
    • Assume now $\lvert L(v)\rvert\leq k+1$. Check if there is some colour $p$ that we can colour and recursively ask if this is possible by using Solve($v_i$,$p$). This excludes the heavy child obviously. Reject if no such colour exists.
    • Check if there is at least a second way to colour $T\setminus T_u$ and call this $p_2$.
    • If yes, free up memory and recursively verify that $T_u$ can be coloured with Solve($u$,0).
      • Notice that we do not have to try $p_1$.
      • This is because it is a tree and $u$ can take any colour it wants.
      • If $u$ has colour $p_1$ we set $r$ to $p_2$ and $p_1$ otherwise.
    • If not then we colour $r$ with $p_1$ and recursively verify with Solve($u$,$p'$) where $p'$ is the apropiate colour in $u$s list if it exists.

Final Proof

• Two main ideas:
  • Storing the colour can be done by storing the index of the list and it can be recomputed.
  • The space used for the colour will depend on the size of the sub-tree. A bracketing idea makes this easier. So the remaining is small.