Finding largest subgraph that contains a given edge and admits a cycle cover I am wondering whether there exists a fast algorithm for the following problem.


  Given a digraph $G$ possibly with loops (that is edges that begin and
  end at the same vertex) and the choice of an edge $e \in G$, what is
  the largest (in terms of number of vertices) subgraph of $G$ that
  contains $e$ and admits a vertex disjoint cycle cover.


ps: sorry for the crosspost, but I originally posted at at stackoverflow and was directed here for a possibly more appropriate crowd...
Deterministically, you can do it as follows: Give your edge $e$ the weight $n+1$ and add a self-loop of weight zero to each node that does not have one so far. Existing edges get weight one. By removing the weight zero loops,
a maximum weight cycle cover in the new graphs induces a partial cycle cover in the old graph that (1) contains your edge $e$ and (2) has a maximum number of edges. The vertices of the partial cycle cover induce the graph you are looking for. If the cycle cover in the new graph does not contain $e$ at all, then
there is no such subgraph.

You can compute a maximum weight cycle cover by reducing it to maximum weight perfect matching.