NP complete graph problems about structural properties (This question is a bit of a &quot;survey&quot;.)
I'm currently working on a problem where I'm trying to partition the edges of a tournament into two sets, both of which are required to fulfill some structural properties. The problem &quot;feels&quot; quite hard, and I fully expect it to be $\mathcal{NP}$-complete. For some reason I'm having a hard time even finding similar problems in literature.
An example of a problem that I would consider comparable to the one I'm dealing with:

Given a weighted tournament $G = (V,E,w)$, is there a feedback arc set in $G$ the edges of which fulfill the triangle inequality?

Note the difference to the traditional feedback arc set (DFAS) problem: I don't care about the size of the set, but I do care whether the set itself has a certain structural property.
Have you encountered any decision problems that feel similar to this? Do you remember whether they were $\mathcal{NP}$-complete or in $\mathcal{P}$? Any and all help appreciated.
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 &amp; 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) .