25
$\begingroup$

I've been trying to find an algorithm to find a maximum vertex cycle cover of a directed graph $G$ — that is, a set of disjoint cycles which contain all the vertices in $G$, with as many cycles as possible (we don't consider individual vertices cycles here). I know that the problem of finding a minimum vertex cycle cover, as well as finding a vertex cycle cover with exactly $k$ cycles is NP-complete. But what about the maximum case?

While I'd find an answer to this interesting in general, the graphs I want to use this for are actually quite constrained by their construction, so maybe even if the problem is NP-complete there might be a polynomial solution for these specific instances.

We have a list of integers $L$, elements $l_i$ and we'll use $S$, elements $s_i$ to refer to $L$ after sorting it. As an example:

$$ L = (1, 3, 2, 5, 0, 7, 4, 2, 6, 0, 8, 1)\\ S = (0, 0, 1, 1, 2, 2, 3, 4, 5, 6, 7, 8) $$

The vertices of the graph will be identified with pairs $(n, i)$ such that $l_i = n$ and $s_i \neq n$. The graph has a directed edge $(n, i) \rightarrow (m, j)$ if and only if $s_j = n$. (A cycle in this graph corresponds to a set of values which can be cyclically permuted such that they'll end up in their sorted position.)

The above example would yield the following graph (using 1-based indices):

enter image description here

One thing that doesn't work is the greedy approach of repeatedly removing the smallest cycle (as this example shows).

Note that this problem is (if I didn't make any mistakes) equivalent to asking how many swaps you need to sort a given list. (Which is what inspired looking into this problem in the first place.)

After some pointers from Juho's answer and a bit more sifting through literature, I've come across the assignment problem which seems very closely related. However, the assignment problem is formulated in terms of a weighted bipartite graph and so far I have not been able to find a way to choose edges and weights to reduce this problem to it. If we wanted to formulate the problem here in terms of minimising a weight function, then an intuitive approach would be to say that the weight of each cycle is $|C|-1$ where $|C|$ is the number of edges (or vertices) in the cycle. (Of course this is equivalent to just setting the weight to $-1$.) That is, the weight depends on the size of the cycle, not the particular edges it includes. But maybe this gives someone another idea for how to reduce the problem.

It also appears that bounding the size of the cycles makes the problem APX-hard for general graphs. This doesn't necessarily imply that the same is true for task of maximising the number of cycles, nor for the specific graphs under consideration here, but it seems to be sufficiently closely related that it could be important.

In summary: Can a maximum vertex disjoint cycle cover be found for the graphs constructed from the above process?

As two asides, I'd also be interested in whether the maximum vertex disjoint cycle cover also has an efficient solution for arbitrary graphs that admit at least one cycle cover (which will probably fall out as an answer to the main question), or whether just determining the number of cycles in the maximum cover (as opposed to the actual edges contained in each) makes the problem any simpler. I'm happy to post these as separate questions if people think they deserve full-fledged answers on their own.

Improve this question
$\endgroup$
6
  • 1
    $\begingroup$ Have you looked at the CS literature on kidney exchanges? The problem seems related, so I wonder if any of the methods there can be applied to this one. This might be a dead end, though... $\endgroup$
    – D.W. ♦
    Feb 2, 2016 at 19:45
  • 1
    $\begingroup$ @D.W. I haven't (I wasn't aware that's a thing). I'll see what I can find, thanks. $\endgroup$
    – Martin Ender
    Feb 2, 2016 at 19:49
  • 1
    $\begingroup$ the problem is indeed similar to kidney exchanges indeed studied from a theoretical pov eg this paper by Roughgarden explains that small cycles are preferred for nearly obvious reasons (p3); the cycle sizes imply "simultaneous operations" & smaller ones decrease risk of pulling off all operations with complications or donors changing minds etc $\endgroup$
    – vzn
    Feb 3, 2016 at 16:20
  • $\begingroup$ @AustinMohr I believe the graphs obtained from the construction I describe will always be decomposable into cycles (and furthermore, no matter which cycle you remove, the remainder will still be decomposable into a cycles). If you want to address general graphs as well, assume that at least one complete cover exists. $\endgroup$
    – Martin Ender
    Feb 5, 2016 at 14:45
  • $\begingroup$ @MartinBüttner In your specific case, if all of the list elements are distinct, would your problem be equivalent to finding the (unique) cycle decomposition of the permutation? $\endgroup$
    – mhum
    Feb 24, 2016 at 1:48

1 Answer 1

Reset to default
4
$\begingroup$

Let a cycle cover of a directed graph be a collection of vertex-disjoint cycles such that each vertex is in exactly one cycle. So if I understand you correctly, given a directed graph $G$, you want a maximum cycle cover, where each cycle is of length at least $k$ (perhaps for $k=2$, or $k=3$ at least). A cycle cover where each cycle is of length at least $k$ is called a $k$-cycle cover.

Deciding if a digraph $G$ has a 2-cycle cover is solvable in polynomial time. The problem of deciding whether $G$ has a 3-cycle cover is NP-complete. The corresponding optimization problem (i.e., finding a maximum weight 3-cycle cover) is APX-complete, and has an $((3/5)-\epsilon)$-approximation algorithm (for any $\epsilon > 0$). The good news here is that one can also compute a maximum weight 2-cycle cover in polynomial time (provided edge weights are nonnegative).

For details and proofs of the above claims, see [1].

[1] Bläser, Markus, and Bodo Manthey. "Two approximation algorithms for 3-cycle covers." Approximation Algorithms for Combinatorial Optimization. Springer Berlin Heidelberg, 2002. 40-50.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Interesting, I'll try to follow the references from that paper. Thanks. (I must have misread something when I thought that k-cycle covers were covers with exactly k cycles. Or maybe that is a different definition used elsewhere.) $\endgroup$
    – Martin Ender
    Feb 15, 2016 at 18:36
  • 2
    $\begingroup$ @MartinBüttner By the way, you will likely want to have a look the PhD thesis of Bläser here. (It's in German, but you will likely have no problem with that :-)). It should cover the details of actually computing a max weight 2-cycle cover. $\endgroup$
    – Juho
    Feb 15, 2016 at 18:41
  • $\begingroup$ Ah wait, I'm actually looking for a minimum-weight 2-cycle cover (as in, one which has a maximal amount of cycles, since the weight is going to be $|V|-n$ where $n$ is the number of cycles in the cover). (Still reading the thesis if that's covered, and I think it is, but your answer seems to focus on maximum weight.) $\endgroup$
    – Martin Ender
    Feb 15, 2016 at 19:13
  • $\begingroup$ Thinking about it some more, I'm not sure it's actually possible to formulate the problem in terms of weights. With equal weights all cycle covers have the same weight. My "cost" for a cycle is actually its length minus 1. That's why I want as many cycles as possible. If this could be formulated in terms of weights it reduces to the assignment problem, but if not I guess I need to keep searching. $\endgroup$
    – Martin Ender
    Feb 16, 2016 at 9:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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