<p>Another problem is Minimum Sum Edge Coloring. The input is a graph and the task is to compute a proper edge-coloring <span class="math-container">$\chi: E\to \mathbb{N}$</span> such that <span class="math-container">$\sum_{e\in E} \chi(e)$</span> is minimal. Here, <em>proper</em> means of course that incident edges receive different colors.</p>
<p>The polynomial-time algorithm for trees has been shown several times, NP-hardness for graphs with treewidth 2 was shown in</p>
<p>Dániel Marx:
Complexity results for minimum sum edge coloring. Discret. Appl. Math. 157(5): 1034-1045 (2009).</p>
<p>In contrast, the Minimum Sum Coloring problem, where the task is to compute a proper vertex coloring is fixed-parameter tractable with respect to the treewidth. This was shown in</p>
<p>Klaus Jansen:
The Optimum Cost Chromatic Partition Problem. CIAC 1997: 25-36</p>

CC BY-SA 4.0
2024-02-28T07:23:25.713Z
2024-02-28T07:23:25.713Z
Christian Komusiewicz
<p>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 vertices at distance two have distinct colors.</p>
<p>In the paper &quot;Distance constrained labelings of graphs of bounded treewidth&quot; by Fiala, Golovach, and Kratochvil it was shown that this is NP-complete on graphs of treewidth 2. The problem was previously known to be in P for trees (&quot;The L(2, 1)-labeling problem on graphs&quot; by Chang and Kuo).</p>

CC BY-SA 4.0
2024-02-23T19:41:33.197Z
Thank you for the answer.
Prafullkumar Tale
CC BY-SA 4.0
2024-02-23T10:42:23.000Z
2024-02-23T10:42:23.000Z
Michael Lampis
<p>Do we know any problem that satisfies the following criteria?</p>
<ol>
<li>It is polynomial-time solvable on trees.</li>
<li>It is NP-complete when restricted to graphs of treewidth 2.</li>
<li>The problem can be encoded only using a graph, i.e., it does not have additional structures like weights on vertices or edges, lists associated with each vertex, a collection of terminals, etc.</li>
</ol>
<p>I am also interested in the problems that partially satisfy these criteria. For example,
some of the problems <a href="https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees">here</a> do not satisfy the first criterium but satisfy the other two. <a href="https://drops.dagstuhl.de/storage/00lipics/lipics-vol214-ipec2021/LIPIcs.IPEC.2021.24/LIPIcs.IPEC.2021.24.pdf" rel="nofollow noreferrer">Metric Dimension</a> satisfies 1 and 3 and is known to be NP-complete for graphs of treewidth 24.
<a href="https://arxiv.org/abs/0911.5143" rel="nofollow noreferrer">Steiner Forest</a> satisfies the first two conditions but not the third one as the input contains an additional structure viz list of terminal pairs.</p>

CC BY-SA 4.0
2024-02-28T13:38:06.190Z
Two problems satisfying 1 and 2 (but not 3): EDGE-DISJOINT PATHS https://www.sciencedirect.com/science/article/pii/S0166218X01002232 and BUDGET-CONSTRAINED FLOW IMPROVEMENT https://www.sciencedirect.com/science/article/abs/pii/S0020019098000702
Florent Foucaud
<cc.complexity-theory><graph-algorithms><np-hardness><np-complete><treewidth>
Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees
Prafullkumar Tale
# Problems that are NP-Complete when restricted to graphs of treewidth 2 but polynomial on trees

(Asked by: username_0 on 2024-02-23)

Do we know any problem that satisfies the following criteria?

1. It is polynomial-time solvable on trees.
2. It is NP-complete when restricted to graphs of treewidth 2.
3. The problem can be encoded only using a graph, i.e., it does not have additional structures like weights on vertices or edges, lists associated with each vertex, a collection of terminals, etc.

I am also interested in the problems that partially satisfy these criteria. For example,
some of the problems [here](https://cstheory.stackexchange.com/questions/1215/np-hard-problems-on-trees) do not satisfy the first criterium but satisfy the other two. [Metric Dimension](https://drops.dagstuhl.de/storage/00lipics/lipics-vol214-ipec2021/LIPIcs.IPEC.2021.24/LIPIcs.IPEC.2021.24.pdf) satisfies 1 and 3 and is known to be NP-complete for graphs of treewidth 24.
[Steiner Forest](https://arxiv.org/abs/0911.5143) satisfies the first two conditions but not the third one as the input contains an additional structure viz list of terminal pairs.

**Tags:** cc.complexity-theory, graph-algorithms, np-hardness, np-complete, treewidth

> **Comments:**
> **username_1**: Two problems satisfying 1 and 2 (but not 3): EDGE-DISJOINT PATHS https://www.sciencedirect.com/science/article/pii/S0166218X01002232 and BUDGET-CONSTRAINED FLOW IMPROVEMENT https://www.sciencedirect.com/science/article/abs/pii/S0020019098000702  

---

## 2 answers

### Answer by username_3 on 2024-02-23. Score: 15 | Accepted answer

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 vertices at distance two have distinct colors.

In the paper "Distance constrained labelings of graphs of bounded treewidth" by Fiala, Golovach, and Kratochvil it was shown that this is NP-complete on graphs of treewidth 2. The problem was previously known to be in P for trees ("The L(2, 1)-labeling problem on graphs" by Chang and Kuo).

> **Comments:**
> **username_0**: Thank you for the answer.  

---

### Answer by username_2 on 2024-02-28. Score: 4

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* means of course that incident edges receive different colors.

The polynomial-time algorithm for trees has been shown several times, NP-hardness for graphs with treewidth 2 was shown in

Dániel Marx:
Complexity results for minimum sum edge coloring. Discret. Appl. Math. 157(5): 1034-1045 (2009).

In contrast, the Minimum Sum Coloring problem, where the task is to compute a proper vertex coloring is fixed-parameter tractable with respect to the treewidth. This was shown in

Klaus Jansen:
The Optimum Cost Chromatic Partition Problem. CIAC 1997: 25-36


---

