8
$\begingroup$

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, 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.

$\endgroup$
  • 1
    $\begingroup$ Why was this question downvoted? $\endgroup$ – Sasho Nikolov Aug 20 at 1:40
  • 5
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Aug 20 at 2:06
  • 5
    $\begingroup$ 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. $\endgroup$ – Chandra Chekuri Aug 20 at 2:47
  • 3
    $\begingroup$ 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}})$. $\endgroup$ – Gamow Aug 20 at 4:34
  • 1
    $\begingroup$ So we know it is doable in $O(c^{\sqrt n})$ for some c which does not fully answer the question. $\endgroup$ – Hermann Gruber Aug 20 at 7:17
7
$\begingroup$

I recommend reading Sections 7 and 14 in the excellent book by Cygan, Fomin, Kowalik, Lokshtanov, Marx, Pilipczuk, Pilipczuk, and Saurabh.

In short, Gu and Tamaki 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 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) 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) 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})}$.

$\endgroup$
  • 2
    $\begingroup$ 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. $\endgroup$ – Saeed Aug 25 at 21:02
  • 2
    $\begingroup$ @Saeed, do we also know that the branchwidth of a planar graph is upper-bounded by $\sqrt{n}$? $\endgroup$ – Alex Golovnev Aug 26 at 21:24
  • 1
    $\begingroup$ 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). $\endgroup$ – Saeed Aug 27 at 7:06

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.