Plenty of hard graph problems are solvable in polynomial time on graphs of bounded treewidth. Indeed, textbooks typically use e.g. independet set as an example, which is a local problem. Roughly, a local problem is a problem whose solution can be verified by examining some small neighborhood of every vertex.Interestingly, even problems (such as Hamiltonian path) of a global nature can still be solved efficiently for bounded treewidth graphs. For such problems, usual dynamic programming algorithms have to keep track of all the ways in which the solution can traverse the corresponding separator of the tree decomposition (see e.g. [1]). Randomized algorithms (based on so-called cut'n'count) were given in [1], and improved (even deterministic) algorithms were developed in [2].I don't know if it's fair to say that many, but at least some global problems can be solved efficiently for graphs of bounded treewidth. So what about problems that remain hard on such graphs? I'm assuming they are also of a global nature, but what else? What separates these hard global problems from global problems that can be solved efficiently? For instance, how and why would known methods fail to give us efficient algorithms for them?For example, one could consider the following problem(s):Edge precoloring extension Given a graph $G$ with some edges colored, decide if this coloring can be extended to a proper $k$-edge-coloring of the graph $G$.Edge precoloring extension (and its list edge coloring variant) is NP-complete for bipartite series-parallel graphs [3] (such graphs have treewidth at most 2).Minimum sum edge coloring Given a graph $G=(V,E)$, find an edge-coloring $\chi : E \to \mathbb{N}$ such that if $e_1$ and $e_2$ have a common vertex, then $\chi(e_1) \neq \chi(e_2)$. The objective is to minimize $E'_\chi(E) = \sum_{e \in E} \chi(e)$, the sum of the coloring.In other words, we have to assign positive integers to the edges of a graph such that adjacent edges receive different integers and the sum of the assigned numbers is minimal. This problem is NP-hard for partial 2-trees [4] (i.e. graphs of treewidth at most 2). Other such hard problems include the edge-disjoint paths problem, the subgraph isomorphism problem, and the bandwidth problem (see e.g. [5] and the references therein). For problems that remain hard even on trees, see this question.[1] Cygan, M., Nederlof, J., Pilipczuk, M., van Rooij, J. M., & Wojtaszczyk, J. O. (2011, October). Solving connectivity problems parameterized by treewidth in single exponential time. In Foundations of Computer Science (FOCS), 2011 IEEE 52nd Annual Symposium on (pp. 150-159). IEEE.[2] Bodlaender, H. L., Cygan, M., Kratsch, S., & Nederlof, J. (2013). Deterministic single exponential time algorithms for connectivity problems parameterized by treewidth. In Automata, Languages, and Programming (pp. 196-207). Springer Berlin Heidelberg.[3] Marx, D. (2005). NPcompleteness of list coloring and precoloring extension on the edges of planar graphs. Journal of Graph Theory, 49(4), 313-324.[4] Marx, D. (2009). Complexity results for minimum sum edge coloring. Discrete Applied Mathematics, 157(5), 1034-1045.[5] Nishizeki, T., Vygen, J., & Zhou, X. (2001). The edge-disjoint paths problem is NP-complete for seriesparallel graphs. Discrete Applied Mathematics, 115(1), 177-186.
What separates easy global problems from hard global problems on graphs of bounded treewidth?
graph theory;graph algorithms;treewidth
Most algorithms for graphs of bounded treewidth are based on some form of dynamic programming. For these algorithms to be efficient, we need to bound the number of states in the dynamic programming table: if you want a polynomial-time algorithm, then you need a polynomial number of states (e.g., n^tw), if you want to show that the problem is FPT, you usually want to show that the number of states is some function of treewidth. The number of states typically corresponds to the number of different types of partial solutions when breaking the graph at some small separator. Thus a problem is easy on bounded-treewidth graphs usually because partial solutions interacting with the outside world via a bounded number of vertices have only a bounded number of types. For example, in the independent set problem the type of a partial solution depends only on which boundary vertices are selected. In the Hamiltonian cycle problem, the type of a partial solution is described by how the subpaths of the partial solution match the vertices of the boundary to each other. Variants of Courcelle's Theorem give sufficient conditions for a problem to have the property that partial solutions have only a bounded number of types. If a problem is hard on bounded-treewidth graphs, then it is usually because of one of the following three reasons. There are interactions in the problem not captured by the graph. For example, Steiner Forest is NP-hard on graphs of treewidth 3, intuitively because the source-destination pairs create interactions between nonadjacent vertices.Elisabeth Gassner: The Steiner Forest Problem revisited. J. Discrete Algorithms 8(2): 154-163 (2010)MohammadHossein Bateni, Mohammad Taghi Hajiaghayi, Dniel Marx: Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth. J. ACM 58(5): 21 (2011)The problem is defined on the edges of the graph. Then even if a part of the graph is attached to the rest of the graph via a bounded number of vertices, there could be many edges incident to those few vertices and then the state of a partial solution can be described only by describing the state of all these edges. This is what made the problems in [3,4] hard.Each vertex can have a large number of different states. For example, Capacitated Vertex Cover is W[1]-hard parameterized by treewidth, intuitively because the description of a partial solution involves not only stating which vertices of the separator were selected, but also stating how many times each selected vertex of the separator was used to cover edges.Michael Dom, Daniel Lokshtanov, Saket Saurabh, Yngve Villanger: Capacitated Domination and Covering: A Parameterized Perspective. IWPEC 2008: 78-90