# Vertex-disjoint cycles passing through a collection of vertices

I am wondering about the complexity of the following problem: given a directed graph $G=(V,E)$ (which may have self-loops at some vertices) and a subset of the vertices $U \subset V$, does there exist a collection of vertex-disjoint cycles $C_1, C_2, \ldots$ such that each $u \in U$ belongs to some cycle $C_i$?

When $U=V$, I can see how to reduce this to the problem of finding a maximum matching in a bipartite graph. I'm not sure how to handle the case when $U$ is a strict subset of $V$.

• I just edited the problem to clarify. The reason Hamiltonian cycle is not a special case is that the number of cycles can be anything you want. This is what makes the problem polynomial time rather than NP-hard when $U=V$. Dec 16 '15 at 20:05
• Thanks, I figured this was the case and deleted my original answer. Have you searched for "directed cycle cover" on Google Scholar? I find many interesting looking hits.
– Juho
Dec 16 '15 at 20:07
• There seem to be a lot of results on cycle covers when $U=V$, for example approximating the cycle cover of minimum weight. I haven't been able to find anything about this problem. Dec 16 '15 at 20:58

If $U$=$V$ it reduces to a matching problem by splitting all of the vertices into a left-vertex and a right-vertex to create a corresponding bipartite graph. All existing edges in the original graph translate to the bipartite graph as low-cost edges directed left-to-right (from the origin's left-vertex to the destination's right-vertex). For each left/right pair, you add a high cost edge connecting the left to the right. (Unless it already had an edge due to a loop, in which case the edge remains low cost.) The minimum cost matching will use as few of those high cost edges as possible. The resulting matching corresponds to a set of vertex-disjoint cycles with the maximum number of total vertices because for each vertex not in a cycle, the high-cost edge is used.
Now assume $U$ is instead a strict subset of $V$. For each vertex not in $U$, consider the high cost edge connecting its left-vertex and right-vertex. Lower the cost of those edges so that the only remaining high-cost edges are the ones connecting left/right vertices in $U$. (Again, if a vertex in $U$ has a loop, the edge is instead low cost.) The minimum cost matching will use as few of those high cost edges as possible, thus maximizing the number of vertices in $U$ that are in cycles.