Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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$.
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.
