# Tag Info

### 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 ...
• 3,698
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 ...
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\}$. ...
• 56
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 ...