<p>I recommend reading Sections 7 and 14 in the excellent book  by <a href="https://link.springer.com/book/10.1007%2F978-3-319-21275-3" rel="noreferrer">Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh</a>.</p>

<p>In short, <a href="https://link.springer.com/article/10.1007/s00453-012-9627-5" rel="noreferrer">Gu and Tamaki</a> give a quadratic time algorithm which finds a branch-decomposition of a planar graph of width at most <span class="math-container">$3\sqrt{n}$</span>. Then <a href="https://www.sciencedirect.com/science/article/pii/009589569190061N" rel="noreferrer">Robertson and Seymour</a> in (5.1) give a tree-decomposition of width less than <span class="math-container">$\frac{9\sqrt{n}}{2}$</span>. Then the classical dynamic programming algorithm (see, e.g., <a href="http://www.cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2" rel="noreferrer">Marx</a>) solves <span class="math-container">$3$</span>-Coloring in time <span class="math-container">$3^{\frac{9\sqrt{n}}{2}}\textrm{poly}(n)&lt;141^{\sqrt{n}}$</span>.</p>

<p>On the other hand, it is known (<a href="https://epubs.siam.org/doi/abs/10.1137/0211025" rel="noreferrer">Lichtenstein</a>) that under the Exponential Time Hypothesis (ETH), the Planar <span class="math-container">$3$</span>-SAT problem is <span class="math-container">$2^{\Omega(\sqrt{n})}$</span>-hard. And a reduction from Planar <span class="math-container">$3$</span>-SAT to Planar <span class="math-container">$3$</span>-Coloring implies that under ETH there is no algorithm solving Planar <span class="math-container">$3$</span>-Coloring in time <span class="math-container">$2^{o(\sqrt{n})}$</span>.</p>

CC BY-SA 4.0
2019-08-25T21:02:22.527Z
We can find exact branch decomposition in polynomial time on planar graphs. This is by paper of Seymour and Thomas: call routing and the rat catcher. So you can remove a factor 3 from the exponent.
Saeed
CC BY-SA 4.0
2019-08-26T21:24:08.420Z
@Saeed, do we also know that the branchwidth of a planar graph is upper-bounded by $\sqrt{n}$?
Alex Golovnev
CC BY-SA 4.0
2019-08-27T07:06:03.620Z
Good point, I remember Fomin et al had a paper showing the upper bound of almost $2\sqrt n$. Don't know what is the best upper bound now. On the other hand I think if we really want to shave off the exponent, it should be possible to directly employ dynamic programming based on branch decomposition, without transformation to tree decomposition (it might already exist in the literature or if not I think it is doable to do it in a good time).
Saeed
CC BY-SA 4.0
2019-08-20T20:46:15.077Z
2019-08-20T20:46:15.077Z
Alex Golovnev
<p>I was wondering if the task of searching for planar 3-colorings is known to be of complexity <span class="math-container">$O\left(c^{\sqrt{n}}\right)$</span> or lower? This feels like it would be an intuitive consequence based from planar separator results, yet in <a href="https://en.wikipedia.org/wiki/Planar_separator_theorem#Exact_solution_of_NP-hard_optimization_problems" rel="noreferrer">wikipedia</a>, it only mentions independent sets, Steiner trees, Hamiltonian cycles, and TSP. Below I include some reasoning which I think almost does achieve this bound.</p>

<p>With a zero reduced decision diagram, (ZDD), I believe you can get <span class="math-container">$O\left(c^{O(log_2(n)\sqrt{n})}\right)$</span>, and I was curious how I could do better. What I came up with is rather rudimentary. Note: throughout, the ZDD I describe is ternary, but I don’t think that greatly matters. For the ZDD, given an ordering, <span class="math-container">$L = \{v_1 \dots v_n\}$</span>, of vertices to color, the number of nodes at step <span class="math-container">$i$</span> will be exponential in respect to the size the frontier, <span class="math-container">$F_i = \{v_k | k &lt; i \land v_k~v_j, j \geq i \}$</span>. </p>

<p>To create your ordering <span class="math-container">$L$</span>, you may create an optimal branch-decomposition tree, <span class="math-container">$b$</span>, in polynomial time, which has width at most <span class="math-container">$\sqrt{n}$</span>. Then, select a random leaf <span class="math-container">$v’$</span> of <span class="math-container">$b$</span> to be your root. With a BFS, weight each edge <span class="math-container">$e$</span> by the number of leaves not connected to <span class="math-container">$v’$</span> if you were to remove <span class="math-container">$e$</span> from <span class="math-container">$b$</span>. Then, do a DFS to finally create <span class="math-container">$L$</span>, always going down the edge furtherest from <span class="math-container">$v’$</span>, choosing the one with least weight if there is a tie, and choosing arbitrarily if there is still a tie. When we reach a leaf, <span class="math-container">$(u,v)$</span> add <span class="math-container">$u$</span>/<span class="math-container">$v$</span> to <span class="math-container">$L$</span> if either is not in <span class="math-container">$L$</span>. Let <span class="math-container">$c_i$</span> be the component induced in <span class="math-container">$b$</span> by the vertices visited when we added <span class="math-container">$v_i$</span> to <span class="math-container">$L$</span>. Then, <span class="math-container">$F_i$</span> is bounded by the branch width times the number of edges <span class="math-container">$x_i$</span> needs to be removed from <span class="math-container">$b$</span> to get the component <span class="math-container">$c_i$</span>. <span class="math-container">$x$</span> is bounded roughly by <span class="math-container">$log_2$</span> of the vertices in <span class="math-container">$b$</span>, which is linear to <span class="math-container">$n$</span> since we’re dealing with planar graphs.</p>

<p>With that, you check all three colors for each node for each of the <span class="math-container">$n$</span> frontiers and you’re done. </p>

CC BY-SA 4.0
2019-08-20T01:40:26.410Z
Why was this question downvoted?
Sasho Nikolov
CC BY-SA 4.0
2019-08-20T01:44:55.863Z
earlier I had no proof attempt included, which I could understand comes off as low-effort and the like.
Zach Hunter
CC BY-SA 4.0
2019-08-20T02:06:19.127Z
It is not hard to find a DP algorithm that runs in $3^k poly(n)$ to check whether a graph with treewidth $k$ can be colored with 3 colors. Since planar graphs have treewidth $O(\sqrt{n})$ your desired time bound follows.
Chandra Chekuri
CC BY-SA 4.0
2019-08-20T02:11:43.590Z
@Chandra Chekuri, I was under the impression that tree-decomposition for planar graphs is not do-able in polynomial time. is there an approximation or sufficiently subexponential algorithm that does this?
Zach Hunter
CC BY-SA 4.0
2019-08-20T02:47:30.257Z
Planar separator theorem suffices to obtain a tree decomposition of width $O(\sqrt{n})$ in polynomial-time. You don't need an exact algorithm for the claimed running time. Also there is a constant factor approximation for treewidth in planar graphs. These are well-known results.
Chandra Chekuri
CC BY-SA 4.0
2019-08-20T04:34:50.070Z
A minor comment: Since the $\sqrt n$ in the exponent has a constant factor in front  of it (stemming from the size of the separator respectively the treewidth), the base $3$ should be a base $const$ everywehere: $O(c^{\sqrt{n}})$.
Gamow
CC BY-SA 4.0
2019-08-20T07:17:59.137Z
So we know it is doable in $O(c^{\sqrt n})$ for some c which does not fully answer the question.
Hermann Gruber
<cc.complexity-theory><graph-algorithms><planar-graphs><graph-colouring>
3-coloring planar graphs in $O\left(3^{n^.5}\right)$?
Zach Hunter
# 3-coloring planar graphs in $O\left(3^{n^.5}\right)$?

(Asked by: username_0 on 2019-08-19)

I was wondering if the task of searching for planar 3-colorings is known to be of complexity $O\left(c^{\sqrt{n}}\right)$ or lower? This feels like it would be an intuitive consequence based from planar separator results, yet in [wikipedia](https://en.wikipedia.org/wiki/Planar_separator_theorem#Exact_solution_of_NP-hard_optimization_problems), it only mentions independent sets, Steiner trees, Hamiltonian cycles, and TSP. Below I include some reasoning which I think almost does achieve this bound.

With a zero reduced decision diagram, (ZDD), I believe you can get $O\left(c^{O(log\_2(n)\sqrt{n})}\right)$, and I was curious how I could do better. What I came up with is rather rudimentary. Note: throughout, the ZDD I describe is ternary, but I don’t think that greatly matters. For the ZDD, given an ordering, $L = \{v\_1 \dots v\_n\}$, of vertices to color, the number of nodes at step $i$ will be exponential in respect to the size the frontier, $F\_i = \{v\_k | k < i \land v\_k~v\_j, j \geq i \}$.

To create your ordering $L$, you may create an optimal branch-decomposition tree, $b$, in polynomial time, which has width at most $\sqrt{n}$. Then, select a random leaf $v’$ of $b$ to be your root. With a BFS, weight each edge $e$ by the number of leaves not connected to $v’$ if you were to remove $e$ from $b$. Then, do a DFS to finally create $L$, always going down the edge furtherest from $v’$, choosing the one with least weight if there is a tie, and choosing arbitrarily if there is still a tie. When we reach a leaf, $(u,v)$ add $u$/$v$ to $L$ if either is not in $L$. Let $c\_i$ be the component induced in $b$ by the vertices visited when we added $v\_i$ to $L$. Then, $F\_i$ is bounded by the branch width times the number of edges $x\_i$ needs to be removed from $b$ to get the component $c\_i$. $x$ is bounded roughly by $log\_2$ of the vertices in $b$, which is linear to $n$ since we’re dealing with planar graphs.

With that, you check all three colors for each node for each of the $n$ frontiers and you’re done.

**Tags:** cc.complexity-theory, graph-algorithms, planar-graphs, graph-colouring
> **Comments:**
> **username_1**: Why was this question downvoted?  
> **username_0**: earlier I had no proof attempt included, which I could understand comes off as low-effort and the like.  
> **username_2**: It is not hard to find a DP algorithm that runs in $3^k poly(n)$ to check whether a graph with treewidth $k$ can be colored with 3 colors. Since planar graphs have treewidth $O(\sqrt{n})$ your desired time bound follows.  
> **username_0**: @Chandra Chekuri, I was under the impression that tree-decomposition for planar graphs is not do-able in polynomial time. is there an approximation or sufficiently subexponential algorithm that does this?  
> **username_2**: Planar separator theorem suffices to obtain a tree decomposition of width $O(\sqrt{n})$ in polynomial-time. You don't need an exact algorithm for the claimed running time. Also there is a constant factor approximation for treewidth in planar graphs. These are well-known results.  
> **username_3**: A minor comment: Since the $\sqrt n$ in the exponent has a constant factor in front  of it (stemming from the size of the separator respectively the treewidth), the base $3$ should be a base $const$ everywehere: $O(c^{\sqrt{n}})$.  
> **username_4**: So we know it is doable in $O(c^{\sqrt n})$ for some c which does not fully answer the question.  

---

## 1 answers

### Answer by username_5 on 2019-08-20. Score: 9 | Accepted answer

I recommend reading Sections 7 and 14 in the excellent book by [Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh](https://link.springer.com/book/10.1007%2F978-3-319-21275-3).

In short, [Gu and Tamaki](https://link.springer.com/article/10.1007/s00453-012-9627-5) give a quadratic time algorithm which finds a branch-decomposition of a planar graph of width at most $3\sqrt{n}$. Then [Robertson and Seymour](https://www.sciencedirect.com/science/article/pii/009589569190061N) in (5.1) give a tree-decomposition of width less than $\frac{9\sqrt{n}}{2}$. Then the classical dynamic programming algorithm (see, e.g., [Marx](http://www.cs.bme.hu/~dmarx/papers/marx-warsaw-fpt2)) solves $3$-Coloring in time $3^{\frac{9\sqrt{n}}{2}}\textrm{poly}(n)<141^{\sqrt{n}}$.

On the other hand, it is known ([Lichtenstein](https://epubs.siam.org/doi/abs/10.1137/0211025)) that under the Exponential Time Hypothesis (ETH), the Planar $3$-SAT problem is $2^{\Omega(\sqrt{n})}$-hard. And a reduction from Planar $3$-SAT to Planar $3$-Coloring implies that under ETH there is no algorithm solving Planar $3$-Coloring in time $2^{o(\sqrt{n})}$.

> **Comments:**
> **username_6**: We can find exact branch decomposition in polynomial time on planar graphs. This is by paper of Seymour and Thomas: call routing and the rat catcher. So you can remove a factor 3 from the exponent.  
> **username_5**: @Saeed, do we also know that the branchwidth of a planar graph is upper-bounded by $\sqrt{n}$?  
> **username_6**: Good point, I remember Fomin et al had a paper showing the upper bound of almost $2\sqrt n$. Don't know what is the best upper bound now. On the other hand I think if we really want to shave off the exponent, it should be possible to directly employ dynamic programming based on branch decomposition, without transformation to tree decomposition (it might already exist in the literature or if not I think it is doable to do it in a good time).  

---

