  For an optimization problem $\Pi$ on graphs whose solutions are vertex sets,
a vertex $v$ is called $c$-essential for $\Pi$ if all solutions of size at most
$c \cdot OPT$ contain $v$. Recent work showed that polynomial-time algorithms
to detect $c$-essential vertices can be used to reduce the search space of
fixed-parameter tractable algorithms solving such problems parameterized by the
size $k$ of the solution. We provide several new upper- and lower bounds for
detecting essential vertices. For example, we give a polynomial-time algorithm
for $3$-Essential detection for Vertex Multicut, which translates into an
algorithm that finds a minimum multicut of an undirected $n$-vertex graph $G$
in time $2^{O(\ell^3)} \cdot n^{O(1)}$, where $\ell$ is the number of vertices
in an optimal solution that are not $3$-essential. Our positive results are
obtained by analyzing the integrality gaps of certain linear programs. Our
lower bounds show that for sufficiently small values of $c$, the detection task
becomes NP-hard assuming the Unique Games Conjecture. For example, we show that
($2-\varepsilon$)-Essential detection for Directed Feedback Vertex Set is
NP-hard under this conjecture, thereby proving that the existing algorithm that
detects $2$-essential vertices is best-possible.
