I am looking for the most efficient algorithm that can solve this problem: Given a directed graph with real-valued edge weights, find a set of directed cycles (no two cycles can share a vertex) that have the maximum sum of weights.
3
-
$\begingroup$ Are all weights nonnegative? $\endgroup$– Max AlekseyevCommented Dec 6, 2019 at 13:20
-
$\begingroup$ @MaxAlekseyev Yes, all weights are nonnegative, however this should make no difference, since if you add some sufficiently large constant to all the weights, they will be nonnegative and the solution should be the same if I am not mistaken. $\endgroup$– Josef OndrejCommented Dec 6, 2019 at 15:32
-
1$\begingroup$ No. Adding large constant will bring a bias: more edges the better. So, not only weight of cycles will play the role, but also the number of edges they contain. $\endgroup$– Max AlekseyevCommented Dec 6, 2019 at 16:22
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
This is known as the maximum weight cycle packing problem. See, for example, this paper. The kidney exchange and barter exhange problems are also relevant.
answered Dec 6, 2019 at 17:41
$\begingroup$
$\endgroup$
1
If no further constraints on like e.g. minimal or maximal length of the individual cycle, then the problem is equivalent to a bipartite weighted matching problem that can be solved in $=(V^2\log V\,+\,VE)$ time cf e.g. Matching (Graph theory) on omniscient wikipedia. The two sets of the bipartite graph consist of the set of vertices in their 'rôle' as sources of edges and as targets of edges.
If the size of individual cycles is however restricted to be at least three or e.g. alternatively not to be longer than three, then the problem becomes NP-hard Valiant, 1979 or Computing Cycle covers without short cycles for the effect of imposing lower bounds and Maximum weight cycle packing in optimal kidney exchange programs for cycle packings with upper bounds.
answered Dec 6, 2019 at 18:22
-
$\begingroup$ just saw that Max Alekseyev already had posted a link to the kidney exchange problem,so credits for that go of course to him. $\endgroup$ Commented Dec 6, 2019 at 18:25