12
$\begingroup$

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.

$\endgroup$
1

2 Answers 2

4
$\begingroup$

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

$\endgroup$
15
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ Thank you for the answer. $\endgroup$ Feb 23 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.