# Graph Isomorphism and Bounded Tree Width

If you read my earlier post, you known that I am fan of treewidth. Who isn’t !! The complexity of Graph Isomorphism (earlier post) is one of the long-standing open problem. Intersecting these two with one of my research interests (space-bounded computation) we get the following open problem :

Open Problem : What is the complexity of graph isomorphism for graphs with bounded treewidth ?

Graphs with treewidth at most $k$ are also called partial $k$-trees. In 1992 Lindell proved that trees (graphs with treewidth=1) can be canonized in logspace [Lindel’92]. What about canonization for $k=2$ ? Recently Datta et. al [DLNTW’09] proved that the canonization of planar graph is logspace-complete. The following simple exercise shows that partial 2-trees are planar graphs. Hence the result of [DLNTW’09] implies that partial 2-trees can be canonized in logspace.

Exercise : Every partial 2-tree is planar.

In fact, canonization of partial 2-trees is settled earlier by [ADK’08]. What about $k=3$ ? Partial 3-trees may not be planar. An example is $K_{3,3}$ itself. The tree width of $K_{3,3}$ is three. I wanted to work on the case of $k=3$ and realized the following simple fact.

Exercise : Partial 3-trees are $K_{5}$-free.

In a follow-up paper to [DLNTW’09], Datta et al [DNTW’10] proved that canonization of $K_{3,3}$-free and $K_{5}$-free graphs is in Log-space. Hence we get the following corollary :

Corollary : Partial 3-trees can be canonized in log-space.

Since the above result is not explicitly mentioned in any papers, I wanted to make it clear in this post. Hence the open problem is for $k \geq 4$. LogCFL is the best known upper bound for graph isomorphism of partial k-trees [DTW’10]. One of the bottleneck, finding a tree decomposition of partial k-tree in logspace, is resolved recently [EJT’10]. The above mentioned papers make use of a decomposition of the input graph into two- or three-connected subgraphs, constructing an appropriate tree of these subgraphs, using the known structural properties of two- and three-connected graphs to canonize these subgraphs and using Lindell’s result to canonize the entire graph. Unfortunately no clean characterization exists for graphs with connectivity at least four. Many long-standing open problems in graph theory are trivial for 2- and 3- connected graphs and open for higher connectivity. A clean characterization of 4-connected graphs seems to be a major bottleneck in improving the space complexity of canonization of partial 4-trees. I am lost 😦

Open Problems

• Is graph isomorphism of partial k-trees (for $k \geq 4$) in logspace ?
• Is canonization of partial k-trees in LogCFL ? The paper of [DTW’10] solves isomorphism only.

References :

• [Lindell’92] Steven Lindell: A Logspace Algorithm for Tree Canonization STOC 1992: pages 400-404
• [DLNTW’09] Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner: Planar Graph Isomorphism is in Log-Space. IEEE Conference on Computational Complexity 2009: 203-214
• [DNTW’10] Samir Datta, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner: Graph Isomorphism for K{3, 3}-free and K5-free graphs is in Log-space. Electronic Colloquium on Computational Complexity (ECCC) 17: 50 (2010)
• [ADK’08] Vikraman Arvind, Bireswar Das, Johannes Köbler: A Logspace Algorithm for Partial 2-Tree Canonization. CSR 2008: 40-51
• [DTW’10] Bireswar Das, Jacobo Torán, Fabian Wagner: Restricted Space Algorithms for Isomorphism on Bounded Treewidth Graphs. STACS 2010: 227-238
• [EJT’10] Michael Elberfeld, Andreas Jakoby, Till Tantau: Logspace Versions of the Theorems of Bodlaender and Courcelle. FOCS 2010: 143-152

# Type Sensitive Depth and Karchmer Wigderson Games

Throughout this post, we will be considering circuits over the basis $\{\vee,\wedge,\neg\}$ where $\{\vee,\wedge\}$-gates have fanin 2 and $\neg$-gates are only applied to input variables. Let $f : \{0,1\}^n \rightarrow \{0,1\}$ be a boolean function on $n$ variables and $G_n$ be a circuit computing $f$. For an output gate $g$, let $g_l$ and $g_r$ be the sub-circuits, whose outputs are inputs to $g$. Let $d(G_n)$ be the depth of circuit $G_n$ and $d(f)$ be the minimum depth of a circuit computing $f$.

Karchmer and Wigderson [KW’90] showed an equivalence between circuit depth and a related problem in communication complexity. It is a simple observation that we can designate the two players as an “and-player” and an “or-player”. Let $S_0, S_1 \subseteq \{0,1\}^n$ such that $S_0 \cap S_1 = \emptyset$. Consider the communication game between two players ($P_{\wedge}$ and $P_{\vee}$), where $P_{\wedge}$ gets $x \in S_1$ and $P_{\vee}$ gets $y \in S_0$. The goal of the players to find a coordinate $i$ such that $x_i \neq y_i$. Let $C(S_1,S_0)$ represent the minimum number of bits they have to communicate in order for both to agree on such coordinate.

Karchmer-Wigderson Theorem : For every function $f : \{0,1\}^n \rightarrow \{0,1\}$ we have $d(f) = C(f^{-1}(1),f^{-1}(0))$.

Karchmer and Wigderson used the above theorem to prove that ‘monotone circuits for connectivity require super-logarithmic depth’. Let $C_{\wedge}(S_1,S_0)$ (resp. $C_{\vee}(S_1,S_0)$) represent the minimum number of bits that $P_{\wedge}$ (resp $P_{\vee}$) has to communicate. We can define type-sensitive depths of a circuit as follows. Let $d_{\wedge}(G_n)$ (resp. $d_{\vee}(G_n)$) represent the AND-depth (resp. OR-depth) of $G_n$.

AND-depth : AND-depth of an input gate is defined to be zero. AND-depth of an AND gate $g$ is max($d_{\wedge}(g_l), d_{\wedge}(g_r)$) + 1. AND-depth of an OR gate $g$ is max($d_{\wedge}(g_l), d_{\wedge}(g_l)$). AND-depth of a circuit $G_n$ is the AND-depth of its output gate.

OR-depth is defined analogously. Let $d_{\wedge}(f)$ (resp. $d_{\vee}(f)$) be the minimum AND-depth (resp. OR-depth) of a circuit computing $f$.

Observation : For every function $f : \{0,1\}^n \rightarrow \{0,1\}$ we have that $C_{\wedge}(f^{-1}(1),f^{-1}(0))$ corresponds to the AND-depth and $C_{\vee}(f^{-1}(1),f^{-1}(0))$ corresponds to the OR-depth of the circuit constructed by Karchmer-Wigderson.

Open Problems :

• Can we prove explicit non-trivial lower bounds of $d_{\wedge}(f)$ (or $d_{\vee}(f)$) of a given function $f$ ? This sort of “asymmetric” communication complexity is partially addressed in [MNSW’98].
• A suitable notion of uniformity in communication games is to be defined to address such lower bounds. More on this in future posts.

References :

• [KW’90] Mauricio Karchmer and Avi Wigderson : Monotone circuits for connectivity require super-logarithmic depth. SIAM Journal on Discrete Mathematics, 3(2):255–265, 1990.
• [MNSW’98] Peter Bro Miltersen, Noam Nisan, Shmuel Safra, Avi Wigderson: On Data Structures and Asymmetric Communication Complexity. J. Comput. Syst. Sci. 57(1): 37-49 (1998)

# Balanced ST-Connectivity

Today’s post is about a new open problem arising from my recent paper  (available on ECCC). The problem is as follows :

Let $G(V,E)$ be a directed graph. Let $G'(V,E')$ be the underlying undirected graph of $G$. Let $P$ be a path in $G'$. Let $e = (u,v)$ be an edge along the path $P$. Edge $e$ is called neutral edge if both $(u,v)$ and $(v,u)$ are in $E$. Edge $e$ is called forward edge if $(u,v) \in E$ and $(v,u) \notin E$. Edge $e$ is called backward edge if $(u,v) \notin E$ and $(v,u) \in E$.

A path (say $P$) from $s \in V$ to $t \in V$ in $G'(V,E')$ is called balanced if the number of forward edges along $P$ is equal to the number of backward edges along $P$. A balanced path might have any number of neutral edges. By definition, if there is a balanced path from $s$ to $t$ then there is a balanced path from $t$ to $s$. The path $P$ may not be a simple path. We are concerned with balanced paths of length at most $n$.

Balanced ST-Connectivity : Given a directed graph $G(V,E)$ and two distinguished nodes $s$ and $t$, decide if there is balanced path (of length at most $n$) between $s$ and $t$.

In my paper, I proved that SGSLOGCFL, a generalization of Balanced ST-Connectivity, is contained in DSPACE(lognloglogn). Details about SGSLOGCFL are in my paper.

Theorem 1 : SGSLOGCFL is in DSPACE(lognloglogn).

Open Problem : Is $SGSLOGCFL \in L$ ?

Cash Prize : I will offer $100 for a proof of $SGSLOGCFL \in L$. I have spent enough sleepless nights trying to prove it. In fact, an alternate proof of Theorem 1 (or even any upper bound better than $O({\log}^2n)$) using zig-zag graph product seems to be a challenging task. Usually people offer cash prizes for a mathematical problem when they are convinced that : • it is a hard problem. • it is an important problem worth advertising. • the solution would be beautiful, requires new techniques and sheds new light on our understanding of related problems. My reason is “All the above”. Have Fun solving it !! A cute puzzle : In Balanced ST-Connectivity we are only looking for paths of length at most $n$. There are directed graphs where the only balanced st-path is super-linear. The example in the following figure shows an instance of Balanced ST-Connectivity where the only balanced path between $s$ and $t$ is of length $\Theta(n^2)$. The directed simple path from $s$ to $t$ is of length $n/2$. There is a cycle of length $n/2$ at the vertex $v$. All the edges (except $(v,u)$) on this cycle are undirected. The balanced path from $s$ to $t$ is obtained by traversing from $s$ to $v$, traversing the cycle clockwise for $n/2$ times and then traversing from $v$ to $t$. Puzzle : Are there directed graphs where every balanced st-path is of super-polynomial size ? Update : The above puzzle is now solved. Open Problems • Is $SGSLOGCFL \in L$ ? • Are there directed graphs where every balanced st-path is of super-polynomial size ? (solved) • More open problems are mentioned in my paper. # Hardness of Graph Isomorphism The complexity of Graph Isomorphism (GI) is one of the major open problems. It is easy to see that $GI \in NP$. It is known that $GI \in NP \cap coAM$. The following theorem states that it is unlikely that GI is NP-complete. Theorem [Schöning’87, BHZ’87] : If GI is NP-complete then the polynomial hierarchy collapses to its second level. The counting version of GI is known to be reducible to its decisional version. A polynomial time algorithm solving GI would be a major breakthrough. The best known algorithm runs in $2^{O(\sqrt{n{\log}n})}$ for graphs with $n$ vertices. Several special cases are shown to be in P. Several problems are known to be GI-hard. See this wikipedia article for details. GI is widely believed to be an NP-intermediate problem. Conjecture : If $P \neq NP$, then GI is neither NP-complete nor in P. Note that if the above conjecture is true then GI is P-hard. Is GI known to be P-hard ? What is the best known hardness of GI ? Well… we know very little about the hardness of GI. The following exercises show that GI is L-hard. Exercise : Consider the following restricted automorphism problem: Given a graph $G = (V,E)$ and two lists of nodes $(x_1, \dots, x_k),(y_1,\dots, y_k)$, is there an automorphism in G mapping $x_i$ to $y_i$ for 1 ≤ i ≤ k ? Show that this problem is reducible to GI. Exercise : Show that Undirected ST-connectivity is reducible to the above mentioned automorphism problem. Torán [Torán’00] proved the following hardness theorem. Informally speaking, GI is hard for all complexity classes defined in terms of the number of accepting computations of a nondeterministic logarithmic space machine. These are the best known hardness results for GI. Theorem [Torán’00] : GI is hard for $NL$, $PL$, $Mod_k{L}$ and $DET$. All these hardness results are under DLOGTIME uniform $AC^0$ many-one reductions. $DET$ is the class of problems $NC^1$ Turing reducible to the determinant [Cook’85]. It is known that $Mod_k{L} \subseteq DET$ and $NL \subseteq C_{=}L \subseteq PL \subseteq DET$. Hence the best known hardness of GI is DET-hardness. However, we do not know the exact complexity of $DET$ i.e., we don’t know where $DET$ lies in terms of the known complexity classes between $NL$ and $NC^2$. In particular, what is the relation between $LogCFL = SAC^1$ and $DET$ ? Torán also showed a randomized logarithmic space reduction from the perfect matching problem to graph isomorphism. More details about the complexity of perfect matching in a future blog post. Open Problems: • Is GI LogCFL-hard ? • Is DET LogCFL-hard ? What is the relation between LogCFL and DET ? This is an independent long-standing open problem. It deserves a separate blog post. • Is $GI \in coNP$ ? A proof of this would imply that “if GI is NP-complete then $NP = coNP$“, improving the above mentioned theorem. • Is GI in P for strongly regular graphs ? The best known algorithm for strongly regular graphs, given by Spielman [Spielman’96], runs in time $n^{O({n^{1/3}}{{\log}n})}$. References : • [BHZ’87] R. Boppana, J. Håstad, and S. Zachos , “Does co-NP have short interactive proofs?”, Information Processing Letters 25(2), pages 127-132, (1987). • [Schöning’87] Uwe Schöning, Graph isomorphism is in the low hierarchy, Proceedings of the 4th Annual Symposium on Theoretical Aspects of Computer Science, 1987, 114–124; also: Journal of Computer and System Sciences, vol. 37 (1988), 312–323 • [Cook’85] Stephen A. Cook, A Taxonomy of Problems with Fast Parallel Algorithms Information and Control 64(1-3): 2-21 (1985) • [Spielman’96] Daniel A. Spielman, Faster isomorphism testing of strongly regular graphsSTOC ’96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing, ACM, pp. 576–584 • [Torán’00] Jacobo Torán, On the Hardness of Graph Isomorphism. FOCS’2000, also: SIAM J. Comput. 33(5): 1093-1108 (2004) # NP intersect coNP NP is the set of languages that have short proofs. coNP is the set of languages that have short refutations. Note that coNP is not the complement of NP. NP $\cap$ coNP is non-empty. It is easy to see that all languages in P are in NP $\cap$ coNP i.e., P $\subseteq$ NP $\cap$ coNP. It is conjectured that P $\subsetneq$ NP $\cap$ coNP. i.e., there are problems in NP $\cap$ coNP that are not in P. Following are some problems in NP $\cap$ coNP that are not known to be in P. Factoring : Given an integer what is the complexity of finding its factors. Every integer always has a unique factorization. Hence, Factoring is very different from the NP-complete problems. The following exercise states that it is highly unlikely that Factoring is NP-complete. On the other hand if Factoring is in P then the world as we know today will be in chaos !! Factoring is conjectured to be an intermediate problem. Exercise : If Factoring is NP-complete then NP = coNP. The first step to solve the above exercise is to show that Factoring is in NP $\cap$ coNP. In fact it is also in UP $\cap$ coUP. Perhaps this is the strongest evidence that P $\subsetneq$ NP $\cap$ coNP. Parity Games : Deciding which of the two players has a winning strategy in parity games is in NP $\cap$ coNP, as well as in UP $\cap$ coUP. Stochastic Games : The problem of deciding which player has the greatest chance of winning a stochastic game is in NP $\cap$ coNP [Condon’92] Lattice Problems : The problems of approximating the shortest and closest vector in a lattice to within a factor of $\sqrt{n}$ is in NP $\cap$ coNP [AR’05]. All the above problems are not known to be in P. Open Problems : • Are there other problems in NP $\cap$ coNP that are not known to be in P. • PPAD, PLS have been defined to understand problems whose structure is different from NP-complete problems. Can we define new complexity classes to study the complexity of the above mentioned problems (and related problems if any) ? • Graph Isomorphism (GI) is also conjectured to be an intermediate problem. It is known that GI is not NP-complete unless Polynomial Hierarchy collapses to its second level. Can we improve this result by showing that GI is in coNP ? Whether GI is in coNP is an interesting open problem for a very different reason also. More on this in a future post. References : • [Condon’92] Anne Condon: The Complexity of Stochastic Games Inf. Comput. 96(2): 203-224 (1992) • [AR’05] Dorit Aharonov, Oded Regev: Lattice problems in NP $\cap$ coNP. J. ACM 52(5): 749-765 (2005) # Logspace vs Polynomial time One of the primary goals of complexity theory is separating complexity classes, a.k.a proving lower bounds. Embarrassingly we have only a handful of unconditional separation results. Separating P from NP is of course the mother of all such goals. Anybody who understands the philosophical underpinnings of the P vs NP problem would love to LIVE to see its resolution. Towards resolving this, we made some (“anti”)-progress (Eg : Relativization, Natural proofs, Algebrization) and have a new geometric complexity theory approach which relies on an Extended-Extended-Extended-Extended-Riemann-Hypothesis !! For more information about the history and status of P vs NP problem read Sipser’s paper [Sipser’92], Allender’s status report [Allender’09] or Fortnow’s article [Fortnow’09]. Today’s post is about the Logspace (L) vs Polynomial time (P) problem, which (in my opinion) is right next to the P vs NP problem in its theoretical importance. I guess many researchers believe that $L \neq P$. Did we make any progress/anti-progress towards resolving the $L \neq P$ conjecture ? Here are two attempts both based on branching programs and appeared in MFCS with a gap of 20 years !! 1) A conjecture by Barrington and McKenzie (BM’89): The problem $GEN$ is defined as follows : $GEN$ : Given an $n \times n$ table filled with entries from $\{1,2,\dots,n\}$, which we interpret as the multiplication table of an $n$-element groupoid, and a subset $S$ of $\{1,2,\dots,n\}$ which includes element 1, determine whether the subgroupoid $$, defined as the closure of $S$ under the groupoid product, includes element $n$. Barrington-McKenzie Conjecture : For each $n > 1$, a branching program in which each node can only evaluate a binary product within an $n$-element groupoid, branching $n$ ways according to the $n$ possible outcomes, must have at least $2^{n-2}$ nodes to solve all $n \times n$ $GEN$ instances with singleton starting set $S$. The problem $GEN$ is known to be P-complete [JL’76]. Barrington-McKenzie Conjecture would imply that $GEN \notin DSPACE({{\log}^k}n)$ for any $k$. In particular, it would imply that $L \neq P$. I don’t know if there is any partial progress towards resolving this conjecture. 2) Thrifty Hypothesis : This is a recent approach by Braverman et. al [BCMSW’09] towards proving a stronger theorem $L \neq LogDCFL$. Stephen Cook presented this approach at Valiant’s 60th birthday celebration and Barriers Workshop. He also announced a$100 prize for solving an intermediate open problem mentioned in his slides.

Tree Evaluation Problem (TEP): The input to the problem is a rooted, balanced $d$-ary tree of height $h$, whose internal nodes are labeled with $d$-ary functions on $[k] = \{1, . . . , k\}$, and whose leaves are labeled with elements of $[k]$. Each node obtains a value in $[k]$ equal to its $d$-ary function applied to the values of its $d$ children. The output is the value of the root.

In their paper they show that $TEP \in LogDCFL$ and conjecture that $TEP \notin L$. They introduce Thrifty Branching Programs and prove that TEP can be solved by a thrifty branching program. A proof of the following conjecture implies that $L \neq LogDCFL$. For more details, read this paper.
Thrifty Hypothesis : Thrifty Branching Programs are optimal among deterministic branching programs solving TEP.

Open Problems :

• My knowledge about the history of L vs P problem is limited.  Are there other approaches/attempts in the last four decades to separate L from P ?
• An intermediate open problem is mentioned in the last slide of these slides. The authors announced \$100 prize for the first correct proof. Read their paper for more open problems.

References :

• [BM’89] David A. Mix Barrington, Pierre McKenzie: Oracle Branching Programs and Logspace versus P. MFCS 1989: 370-379
• [BCMSW’09] Mark Braverman, Stephen A. Cook, Pierre McKenzie, Rahul Santhanam, Dustin Wehr: Branching Programs for Tree Evaluation. MFCS 2009: 175-186
• [Sipser’92] Michael Sipser: The History and Status of the P versus NP Question STOC 1992: 603-618
• [Allender’09] Eric Allender: A Status Report on the P Versus NP Question. Advances in Computers 77: 117-147 (2009) [pdf]
• [Fortnow’09] Lance Fortnow: The status of the P versus NP problem. Commun. ACM 52(9): 78-86 (2009) [pdf]
• [JL’76] Neil D. Jones, William T. Laaser: Complete Problems for Deterministic Polynomial Time. Theor. Comput. Sci. 3(1): 105-117 (1976)

# Approximating TreeWidth

Today’s post is about TreeWidth. When I first came across treewidth, I became an instant fan.

Definition : A tree-decomposition of a graph $G(V,E)$ is a pair $(\{X_i | i \in I \}, T=(I,F))$ where $\{X_i | i \in I \}$ is a family of subsets of $V$, one for each node of $T$, and $T$ is a tree such that :

• The union of the sets $X_i$ is equal to $V$.
• for all edges $(v,w) \in E$, there exists an $i \in I$ with $v \in X_i$ and $w \in X_i$.
• for all $i,j,k \in I$ : if $j$ is on the path from $i$ to $k$ in $T$, then $X_i \cap X_k \subseteq X_j$.

The treewidth of a tree-decomposition is $max_{i \in I}|X_i| - 1$. The treewidth of a graph $G$ is the minimum treewidth over all possible tree-decompositions of $G$.

Following are some interesting facts :

• Exercise : TreeWidth of a tree is 1.
• Exercise : TreeWidth of a clique on $n$ vertices in $n-1$.
• Determining whether treewidth of a given graph is at most $k$ is NP-complete.
• See [BGHK’95] for interesting applications of treewidth Eg : Choleski factorization on sparse symmetric matrices.
• There is an analogous notion of pathwidth which is also NP-complete.

Approximating tree-width : Bodlaender et. al [BGHK’95] presented an $O({\log}n)$ factor approximation algorithm for treewidth. This also gives an $O({{\log}^2}n)$ factor approximation algorithm for pathwidth. Their algorithm works by repeatedly finding vertex separators and uses Leighton-Rao’s algorithm at its heart. The main insights from their paper are as follows :

• If there is a factor $\alpha$ approximation algorithm for vertex separator then there is an $O(\alpha)$ approximation algorithm for treewidth.
• if there is a factor $\beta$ approximation algorithm for treewidth then there is an $O(\beta{\log}n)$ approximation algorithm for pathwidth.

In 1995 the best known approximation factor for vertex separator was $O({\log}n)$. Feige, Hajiaghayi and Lee [FHL’2008] improved this to $O(\sqrt{{\log}n})$. Hence we have $O(\sqrt{{\log}n})$ and $O(\sqrt{{\log}n}{\cdot}{\log}n)$ factor approximation factors for treewidth and pathwidth respectively.

Special cases : What about computing treewidth of restricted classes of graphs ?

• When $k$ is any fixed constant, the graphs with treewidth $k$ can be recognized, and a width $k$ tree decomposition can be constructed for them, in linear time [Bodlaender’96].
• Seymour and Thomas [ST’] showed that branchwidth of planar graphs can be computed in polynomial time. This implies a factor 3/2 approximation for treewdith of planar graphs.

Bounded TreeWidth : If the treewidth of a graph $G$ is bounded by some fixed constant $k$, then several problems (that are NP-hard (even PSPACE-hard) for general graphs) can be solved in polynomial-time and often linear time !! Some of them include Maximum Independent set (hence maximum Clique), Hamiltonian cycle, Graph Isomorphism. Instead of listing all these problems, lets look at the following awesome theorem.

Courcelle’s Theorem : Any property of graphs definable in monadic second-order logic (MSO2) can be decided in linear time on any class of graphs of bounded tree-width. In other words, MSO2 is fixed-parameter tractable on any such class of graphs.

More information about Courcelle’s theorem can be found in this book. A recent paper (appeared today on arXiv) proved the following lower bound.
Theorem [KT’2010] : If C is any class of graphs which is closed under taking sub-graphs and whose tree-width is not bounded by a poly-logarithmic function then MSO2-model checking is intractable on C (under suitable assumptions from complexity theory)
There are several open problems related to treewidth, pathwidth, branchwidth and the related cops-robber games. Following are some that interest me :

Open Problems :

• Perhaps the most interesting open question is to obtain a constant factor approximation for treewidth.
• Bodlaender et. al ruled out absolute approximation algorithm, (unless P = NP) for treewidth and pathwidth. This is the best known hardness. Can we even rule out PTAS for treewidth ? Note that the hardness of treewidth implies the hardness of vertex separator (with constant factor blow-up).
• How hard is computing treewidth of planar graphs ? NP-hardness is not known. Many researchers I talked to, believe that treewidth of planar graphs can be computed in polynomial-time.
• Can the lower bound from [KT’2010] be improved ? In this context, it is interesting to note that Maximum Independent Set can be solved in polynomial time even when the treewidth is bounded by $O({\log}n)$.
• Datta et. al [DLNTW’2009] showed that planar graph isomorphism is in logspace. Is isomorphism for graphs with bounded treewidth in logspace ? I asked this question to some researchers, and this seems to be an open problem.

References :

• [BGHK’95] Hans L. Bodlaender, John R. Gilbert, Hjálmtyr Hafsteinsson, Ton Kloks: Approximating Treewidth, Pathwidth, Frontsize, and Shortest Elimination Tree. J. Algorithms 18(2): 238-255 (1995)
• [Bodlaender’96] Bodlaender, Hans L. : A linear time algorithm for finding tree-decompositions of small treewidth. SIAM Journal on Computing 25 (6): 1305–1317 (1996)
• [KT’2010] Stephan Kreutzer, Siamak Tazari Lower Bounds for the Complexity of Monadic Second-Order Logic arXiv:1001.5019

• [FHL’2008] Uriel Feige, MohammadTaghi Hajiaghayi, James R. Lee: Improved Approximation Algorithms for Minimum Weight Vertex Separators. SIAM J. Comput. 38(2): 629-657 (2008)
• [ST’90] PaulD.Seymour and Robin Thomas : Call Routing and the Ratcacher. Combinatorica 14(2): 217-241 (1994)
• [DLNTW’2009] Samir Datta, Nutan Limaye, Prajakta Nimbhorkar, Thomas Thierauf, Fabian Wagner: Planar Graph Isomorphism is in Log-Space. IEEE Conference on Computational Complexity 2009: 203-214