What separates easy global problems from hard global problems on graphs of bounded treewidth?

Question

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). NP‐completeness 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 series–parallel graphs. Discrete Applied Mathematics, 115(1), 177-186.

Answer 1

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.

1. 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, Dániel Marx: Approximation Schemes for Steiner Forest on Planar Graphs and Graphs of Bounded Treewidth. J. ACM 58(5): 21 (2011)

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

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

Answer 2

My suggestion would be to look carefully at Courcelle's theorem, that problems expressible in (certain extensions of) monadic second order logic have FPT algorithms when parameterized by treewidth. My suspicion is that this covers many or most of the known examples of FPT problems for these graphs. In this view, your local/global distinction seems to be closely related to the distinction between problems expressible in existential MSO vs problems that have higher levels of quantification in their MSO formulations. To return to your actual question, lack of an MSO formulation (which can be proven unconditionally in many cases using ideas related to the Myhill–Nerode theorem) would be evidence towards lack of an FPT algorithm (harder to prove without complexity theoretic assumptions).

Answer 3

I think one of such examples is the sparsest cut problem. Uniform sparsest cut problem is solvable on graphs of bounded tree width but weighted sparsest cut problem is not even approximable (better than 17/16) in graphs of bounded treewidth.

There are many different variants of sparsest cut problem but one of the well known one is as follows.

Given a graph $G=(V,E)$ and a weight function $w:E(G)\rightarrow N$, find an edge cut $E(S,V\setminus S) \subseteq E(G)$ for $S \subset V$ such that $\frac{W(E(S,V\setminus S))}{|S||V\setminus S|}$ is minimized over all possible such cuts. (for $E'\subseteq E(G)$ we have $W(E')=\sum_{e\in E'}w(e)$, also we can simply change the problem definition to decision version).

The main ingredient is made of two things:

1. Additional functions, like here the weight function. But still there are some problems with weight function that are not very hard in undirected graphs of bounded tree width.

2. The nature of the sparsest cut problem. Actually existence of more than one dependency for dynamic programming in the definition of the problem. Intuitively the good solution is the one that we partition a graph (by removing some edges) into two almost equal size, on the other hand in this partition we delete as fewest number of edges that we use. The reason that the problem is hard in bounded treewidth graph is that we should apply dynamic programming in two direction, but both directions are depended to each other.

In general, if the problem is in such a way that needs more than one dimension for dynamic programming and also those dimensions are depended to each other then the problem has potential to be hard in graphs of bounded tree width. We can see this pattern in both of problems in the question as well as for the sparsest cut problem. (In the first problem we want to keep previous coloring on the other hand keep coloring as small as possible, in the second problem obviously there are two functions which are dependent to each other)