# Tag Info

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