# Diameter vs. Tractability

I would like to find examples of (unweighted) optimization problems $$\Pi$$ that satisfy 1) or 2):

1) $$\Pi$$ is NP-hard but polytime solvable in the class of graphs with diameter $$\le k$$, for all $$k\ge 1$$.

2) there is a $$k_0\ge 1$$ such that $$\Pi$$ is polytime tractable in the class of graph with diameter at most $$k_0$$ but NP-hard in the class of graphs with diameter at most $$k_0+1$$.

Any ideas ? What about DominatingSet for instance ?

• Are your graphs directed or indirected? Are they (strongly) connected? Is the diameter defined as the largest distance including infinity or the largest finest distance? Please clarify. PS. To the moderator: please convert into a comment. I don't have enough score to comment. – MdAyq Oct 25 at 21:40

For part (2), dominating set clearly is polynomial in graphs of diameter 1 (just pick a vertex within distance one from everything as your dominating set) but hard for graphs of diameter 2. To reduce from dominating set in arbitrary graphs to graphs of diameter 2, start with an arbitrary hard instance $$G$$ of dominating set with $$n$$ vertices $$v_i$$. Add $$n$$ more vertices $$u_i$$, and an additional new vertex $$c$$, with each $$u_i$$ adjacent to $$v_i$$ and to $$c$$. Call the resulting diameter-2 graph $$G'$$. Then $$G'$$ has dominating sets formed by adding $$c$$ to any dominating set of $$G$$. However, the dominating sets of $$G'$$ that avoid $$c$$ must have size at least $$n$$ because they include at least one vertex from each $$u_i$$$$v_i$$ pair.