I think there are lot of similar problems. Here are two in vertex version and one in edge version:

1. Does a given graph have an independent feedback vertex set? (we don't care about the size of the set). This problem is NP-complete; the proof can be derived from the proof of Theorem 2.1 in Garey, Johnson & Stockmeyer.

2. Does a given graph have a vertex cover that induces a tree? (we don't care about the size of the set). This paper gives an NP-completeness proof for this problem (Theorem 2); even for bipartite graphs.

3. Does a given graph have a dominating edge set the edges of which form an induced $1$-regular subgraph? (also known as dominating induced matching or efficient edge dominating; the vertex version is given in the second answer by Mohammad. Again, we don't care about the size of the set). This problem is NP-complete (well-known, first proved here), even for planar bipartite graphs.

The first two problems are particular examples of the problem class called stable-$\pi$: Let $\pi$ be a graph property. Does a given graph have a vertex cover satisfying $\pi$? More NP-complete cases as well as polynomially solvable cases can be found in this and in this paper (and the refs given there) .

I think there are lot of similar problems. Here are two in vertex version and one in edge version:

1. Does a given graph have an independent feedback vertex set? (we don't care about the size of the set). This problem is NP-complete; the proof can be derived from the proof of Theorem 2.1 in Garey, Johnson & Stockmeyer.

2. Does a given graph have a vertex cover that induces a tree? (we don't care about the size of the set). This paper gives an NP-completeness proof for this problem (Theorem 2); even for bipartite graphs.

3. Does a given graph have a dominating edge set the edges of which form an induced $1$-regular subgraph? (also known as dominating induced matching or efficient edge dominating; the vertex version is given in the second answer by Mohammad. Again, we don't care about the size of the set). This problem is NP-complete (well-known, first proved here), even for planar bipartite graphs.

The first two problems are particular examples of the problem class called stable-$\pi$: Let $\pi$ be a graph property. Does a given graph have a vertex cover satisfying $\pi$? More NP-complete cases as well as polynomially solvable cases can be found in this and in this paper (and the refs given there) .

I think there are lot of similar problems. Here are two in vertex version and one in edge version:

1. Does a given graph have an independent feedback vertex set? (we don't care about the size of the set). This problem is NP-complete; the proof can be derived from the proof of Theorem 2.1 in Garay et al..

2. Does a given graph have a vertex cover that induces a tree? (we don't care about the size of the set). This paper gives an NP-completeness proof for this problem (Theorem 2); even for bipartite graphs.

3. Does a given graph have a dominating edge set the edges of which form an induced $1$-regular subgraph? (also known as dominating induced matching or efficient edge dominating; the vertex version is given in the second answer by Mohammad. Again, we don't care about the size of the set). This problem is NP-complete (well-known), even for planar bipartite graphs.

I think there are lot of similar problems. Here are two in vertex version and one in edge version:

1. Does a given graph have an independent feedback vertex set? (we don't care about the size of the set). This problem is NP-complete; the proof can be derived from the proof of Theorem 2.1 in Garey, Johnson & Stockmeyer.

2. Does a given graph have a vertex cover that induces a tree? (we don't care about the size of the set). This paper gives an NP-completeness proof for this problem (Theorem 2); even for bipartite graphs.

3. Does a given graph have a dominating edge set the edges of which form an induced $1$-regular subgraph? (also known as dominating induced matching or efficient edge dominating; the vertex version is given in the second answer by Mohammad. Again, we don't care about the size of the set). This problem is NP-complete (well-known, first proved here), even for planar bipartite graphs.

The first two problems are particular examples of the problem class called stable-$\pi$: Let $\pi$ be a graph property. Does a given graph have a vertex cover satisfying $\pi$? More NP-complete cases as well as polynomially solvable cases can be found in this and in this paper (and the refs given there) .