3
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ 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$. $\endgroup$ – Taylor R. Dec 16 '15 at 20:05
  • $\begingroup$ 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. $\endgroup$ – Juho Dec 16 '15 at 20:07
  • $\begingroup$ 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. $\endgroup$ – Taylor R. Dec 16 '15 at 20:58
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.