patternMinor
Is there an efficient algorithm for this vertex cycle cover problem?
Viewed 0 times
thiscyclecoverproblemvertexefficientalgorithmforthere
Problem
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):
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
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):
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
Solution
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.
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.
Context
StackExchange Computer Science Q#52724, answer score: 4
Revisions (0)
No revisions yet.