26
$\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?

Improve this question
$\endgroup$
6
  • 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
    Commented Sep 11, 2015 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
    Commented Sep 11, 2015 at 19:15
  • 6
    $\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
    Commented Sep 12, 2015 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
    Commented Sep 12, 2015 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
    Commented Sep 12, 2015 at 16:27

1 Answer 1

Reset to default
13
$\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.

Improve this answer
$\endgroup$
2
  • 1
    $\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$
    – Antoine Amarilli 'a3nm'
    Commented Sep 12, 2015 at 10:29
  • 1
    $\begingroup$ @a3nm: it dates back to at least 1993, since Hans Bodlaender mentioned it in his survey "A Tourist Guide through Treewidth". Surely there must be an earlier explicit mention but I haven't yet been able to find it. $\endgroup$
    – Anthony Labarre
    Commented Apr 14, 2020 at 13:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.