3

The problem is still $\mathsf{NP}$-hard. For example, take a hard instance $G = (V,E)$ of the original maximum independent set problem. Add a new vertex set $V'$ to the graph such that $|V'| = |V|$ and $V'$ forms a complete graph. Also, there are no edges between $V$ and $V'$. Let the new graph be $G' = (V' \cup V, E')$ which is also a hard instance. And, $|...


1

You can use Clarkson's algorithm to find the smallest (non-degenerate) enclosing triangle in $O(d\log^2 n)$ expected time, where $d$ is the dimension of your input. So, for constant dimensions, it takes $O(\log^2 n)$ expected time. The algorithms is applicable, because the smallest triangle problem is an LP-type problem. Clarkson's algorithm has many ...


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