# Tag Info

4

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

3

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$-approximation, and that this factor is actually optimal by a reduction to clique. I skimmed it, so I might be missing some subtle points, but the idea of the proof ...

1

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 standard, to the end. Here is the first lemma. Most likely this is already in the Monma and Suri paper. Given any bipartition $(C_1, C_2)$ of $G$, let \$W(C_1, ...

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