12

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 do not satisfy the first criterium but satisfy the other two. Metric Dimension satisfies 1 and 3 and is known to be NP-complete for graphs of treewidth 24. Steiner Forest satisfies the first two conditions but not the third one as the input contains an additional structure viz list of terminal pairs.

Florent Foucaud
  • 2,153
  • 12
  • 27
Prafullkumar Tale
  • 123
  • 4
  • 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 – Florent Foucaud Feb 28 '24 at 13:38

2 Answers2

15

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

Michael Lampis
  • 3,698
  • 22
  • 31
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

Christian Komusiewicz
  • 1,802
  • 13
  • 21