We consider extension variants of Vertex Cover, Independent Set, Connected Vertex Cover and Non-Separating Independent Set. Given a graph G = (V, E) and a vertex set U ⊆ V, the Ext VC (resp. the Ext CVC) is asked if there exists a minimal vertex cover (resp. connected vertex cover) S with U ⊆ S, and the Ext IS (resp. the Ext NSIS) is asked if there exists a maximal independent set (resp. non-separating independent set) S with S ⊆ U.

Possibly contradicting intuition, these problems tend to be NP-complete, even in graph classes where the classical problem can be solved efficiently. Yet, we exhibit some graph classes where the extension variant remains polynomial-time solvable. We also study the Price of Extension (PoE), a measure that reflects the distance of a vertex set U to its maximum efficiently computable subset that is extensible to a minimal connected vertex cover, and provide negative and positive results for PoE in general and special graphs.