Hardness of Minimum Barrier Shrinkage and Minimum Installation Path

Sergio Cabello, Éric Colin de Verdière

In the Minimum Installation Path problem, we are given a graph $G$ with edge weights $w(.)$ and two vertices $s,t$ of $G$. We want to assign a non-negative power $p(v)$ to each ver…