<p>For part (1), if you allow additional restrictions on your graph class, then independent set, Hamiltonian circuit, dominating set, etc., are NP-hard on arbitrary planar graphs but FPT on planar graphs of bounded diameter (because in planar graphs a bound on diameter implies a bound on treewidth). You can turn this into an artificial problem that is NP-hard on arbitrary graphs but FPT on arbitrary graphs of bounded diameter e.g. by asking whether the graph has either a Hamiltonian cycle or a Kuratowski subgraph.</p>

<p>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 <span class="math-container">$G$</span> of dominating set with <span class="math-container">$n$</span> vertices <span class="math-container">$v_i$</span>. Add <span class="math-container">$n$</span> more vertices <span class="math-container">$u_i$</span>, and an additional new vertex <span class="math-container">$c$</span>, with each <span class="math-container">$u_i$</span> adjacent to <span class="math-container">$v_i$</span> and to <span class="math-container">$c$</span>. Call the resulting diameter-2 graph <span class="math-container">$G'$</span>. Then <span class="math-container">$G'$</span> has dominating sets formed by adding <span class="math-container">$c$</span> to any dominating set of <span class="math-container">$G$</span>. However, the dominating sets of <span class="math-container">$G'$</span> that avoid <span class="math-container">$c$</span> must have size at least <span class="math-container">$n$</span> because they include at least one vertex from each <span class="math-container">$u_i$</span>–<span class="math-container">$v_i$</span> pair.</p>

CC BY-SA 4.0
2019-10-25T23:21:55.033Z
2019-10-25T23:21:55.033Z
David Eppstein
<p>I would like to find examples of (unweighted) optimization problems <span class="math-container">$\Pi$</span> that satisfy 1) or 2):</p>

<p>1) <span class="math-container">$\Pi$</span> is NP-hard but polytime solvable in the class of graphs with diameter <span class="math-container">$\le k$</span>, for all <span class="math-container">$k\ge 1$</span>.</p>

<p>2) there is a <span class="math-container">$k_0\ge 1$</span> such that <span class="math-container">$\Pi$</span> is polytime tractable in the class of graph with diameter at most <span class="math-container">$k_0$</span> but NP-hard in the class of graphs with diameter at most <span class="math-container">$k_0+1$</span>.</p>

<p>Any ideas ? What about DominatingSet for instance ?</p>

CC BY-SA 4.0
2019-10-25T21:40:43.253Z
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
<graph-algorithms><np-hardness><fixed-parameter-tractable><diameter>
Diameter vs. Tractability
Mathieu Mari
# Diameter vs. Tractability

(Asked by: username_0 on 2019-10-25)

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 ?

**Tags:** graph-algorithms, np-hardness, fixed-parameter-tractable, diameter

> **Comments:**
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2019-10-25. Score: 4 | Accepted answer

For part (1), if you allow additional restrictions on your graph class, then independent set, Hamiltonian circuit, dominating set, etc., are NP-hard on arbitrary planar graphs but FPT on planar graphs of bounded diameter (because in planar graphs a bound on diameter implies a bound on treewidth). You can turn this into an artificial problem that is NP-hard on arbitrary graphs but FPT on arbitrary graphs of bounded diameter e.g. by asking whether the graph has either a Hamiltonian cycle or a Kuratowski subgraph.

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.


---

