22
$\begingroup$

For a constant $k \in \mathbb{N}$, one can determine in linear time, given an input graph $G$, whether its treewidth is $\leq k$. However, when both $k$ and $G$ are given as input, the problem is NP-hard. (Source).

However, when the input graph is planar, much less seems to be known about the complexity. The problem was apparently open in 2010, a claim that also appeared in this survey in 2007 and on the Wikipedia page for branch decompositions. Conversely, the problem is claimed NP-hard (without proof of reference) in an earlier version of the previously mentioned survey, but I assume this is an error.

Is it still open to determine the complexity of the problem, given $k \in \mathbb{N}$ and a planar graph $G$, of determining $G$ has treewidth $\leq k$? If it is, was this claimed in a recent paper? Are any partial results known? If it isn't, who solved it?

$\endgroup$
  • 1
    $\begingroup$ Interesting question, cheers for rebooting the survey. To chip in my 2 cents, I believe the original source for the linear time proof is Bodlaender but the constant factor hidden by the asymptotic complexity notation is enormous. Perhaps an interesting spin-off / extension to your question would be whether the planar restriction allows for a more practical constant factor in this context? $\endgroup$ – Fasermaler Sep 11 '15 at 18:41
  • 2
    $\begingroup$ I think that it is a "famous and old problem", so if you don't find a paper it is probably still an open problem. Other "evidences": Lecture from course Graph Algorithms, Applications and Implementations (2015), Lecture from course Graphs & Algorithms: Advanced Topics (2014), Encyclopedia of algorithms (2008). $\endgroup$ – Marzio De Biasi Sep 11 '15 at 19:15
  • 5
    $\begingroup$ @Sariel: It can be approximated within a constant factor (3/2) by using the fact that it and branchwidth are within a constant of each other and planar branchwidth can be computed in polynomial time. Also it can be approximated within log for all graphs using Leighton–Rao; see kintali.wordpress.com/2010/01/28/approximating-treewidth $\endgroup$ – David Eppstein Sep 12 '15 at 3:19
  • 2
    $\begingroup$ @Fasermaler the first step in Bodlaender's algorithm (and previous algorithms that were FPT but not linear time) is to compute an approximate tree decomposition on which one can use dynamic programming to find the optimal decomposition. The tighter the approximation, the faster the second step. So the fact that tighter approximations to planar treewidth can be found using branchwidth seems likely to lead to better dependence on the parameter (at the expense of going back up to polynomial from linear). But I don't know of papers that analyze this carefully. $\endgroup$ – David Eppstein Sep 12 '15 at 3:59
  • 4
    $\begingroup$ Regarding the problem of approximating treewidth. An $\alpha$-approximation for finding sparse/balanced node-separators will give an $O(\alpha)$-approximation for treewidth. Thus, in general graphs we will get $O(\sqrt{\log n})$ via ARV/Feige-Lee-Hajiaghayi and $O(1)$ in planar and proper minor-closed families. For general graphs one can get $O(\sqrt{\log k})$ where $k$ is treewidth. $\endgroup$ – Chandra Chekuri Sep 12 '15 at 16:27
12
$\begingroup$

As far as I know the NP-completeness of computing the treewidth of a planar graph is still open. The most recent reference I know is a survey by Bodlaender from 2012 called `Fixed-Parameter Tractability of Treewidth and Pathwidth' that appeared in the festschrift for Mike Fellows' 65th birthday. The problem is listed in the conclusion of the survey.

$\endgroup$
  • $\begingroup$ Thanks! (And thanks also to @MarzioDeBiasi for suggesting other references.) Just out of curiosity, does someone also happen to know when the problem was first posed? $\endgroup$ – a3nm Sep 12 '15 at 10:29

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.