15 votes

Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

L(2,1)-labeling is such a problem. The input is (just) a graph and we want to color it using the minimum number of colors so that neighboring vertices have colors that differ by at least 2 and ...
Michael Lampis's user avatar
4 votes
Accepted

Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

Another problem is Minimum Sum Edge Coloring. The input is a graph and the task is to compute a proper edge-coloring $\chi: E\to \mathbb{N}$ such that $\sum_{e\in E} \chi(e)$ is minimal. Here, proper ...
Christian Komusiewicz's user avatar
4 votes
Accepted

Tree decompositions with unique witness for each edge

I'm afraid the answer to both of your questions is no. Consider a graph $(V_n, E_n)$ with $V_n = \{1,...,n+2\}$ and $E = \{\{i,i+1\} | 1 \leq i \leq n+1\} \cup \{\{i,i+2\} \mid 1 \leq i \leq n\}$. ...
Corto's user avatar
  • 56
3 votes
Accepted

What is the treewidth of the 3D-grid (mesh or lattice) with sidelength n?

It is $\Theta(n^2)$. The argument to prove the lower bound is that we can send an all-pairs concurrent flow of value $1$ and congestion $O(n^4)$, i.e., we can simultaneously send one unit of flow ...
Laakeri's user avatar
  • 1,766

Only top scored, non community-wiki answers of a minimum length are eligible