4 votes

Diameter vs. Tractability

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 ...
user avatar
3 votes

Finding the size $k$ subset in a metric space that maximizes the min distance between elements

From a quick Google search, it looks like your problem is sometimes called (metric) "facility dispersion." This paper by Ravi, Rosenkrantz, and Tayi seems to prove that your heuristic is a $2$-...
user avatar
  • 740
1 vote

partitioning points in the plane into two clusters to minimize maximum cluster diameter

Theorem 1. There is an $O(n\log n)$-time algorithm for the problem in the post. Proof. We first state two utility lemmas, for an arbitrary edge-weighted graph $G$. We postpone their proofs, which are ...
user avatar
  • 8,133

Only top scored, non community-wiki answers of a minimum length are eligible