3 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
2 votes

Research masters programs in theoretical computer science (with a focus on complexity theory)

You may find this link useful https://www.cs.princeton.edu/~smattw/masters/masters.html (I would have commented, but my reputation is too low)
Matan Shtepel's user avatar

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