2
$\begingroup$

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 ?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – MdAyq Oct 25 at 21:40
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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