1
$\begingroup$

I need to determine a matching with maximal weight-sum for a cycle graph with positive, negative and zero edge-weights.

Question:

What is the fastest way of calculating such a matching?

Because of the simple structure of the graph it seems that $O(n^2)$ should be possible.

Improve this question
$\endgroup$
3
  • $\begingroup$ Apparently there are O(n) dynamic programming algorithms for trees. (math.stackexchange.com/questions/320481/…) So you could iterate over each edge and apply the DP algorithm on the remaining path. This gives a O(n^2) algo. $\endgroup$
    – dbal
    Commented Apr 1 at 14:17
  • 2
    $\begingroup$ @dbal thanks for the hint to the trees; I think that generalizes to an O(n) algorithm for cycles; if we duplicate say vertex 0 an make that the start and lend of a path, the we can have three cases: a) the first edge but not the last edge is in the matching; b) the last but not the first edge is in the matching; c) neither the first nor the last edge is in the matching. $\endgroup$
    – Manfred Weis
    Commented Apr 1 at 15:35
  • 1
    $\begingroup$ You might as well omit any edges with nonpositive weight. It might also be interesting to compare the DP approach to the natural (set packing) IP approach with a binary variable for each edge and a conflict constraint for each node. $\endgroup$
    – RobPratt
    Commented Apr 1 at 18:20

1 Answer 1

Reset to default
1
$\begingroup$

With inspiration from the comments I arrived at the following idea:

the maximum weight matching on the cycle is converted to a maximum weight matching on a path that is generated by splitting a vertex, preferably between two non-positive edges or a positive and non-positive edge.

If we have to split between two positive edges and both are in the maximum weight matching of the resulting path graph, we remove the lighter of the two edges to obtain the heaviest cycle matching.

A key observation is that in a maximum weight matching of a path graph one can't have a contiguous sequence of more than two edges of positive weight that are not in the matching.

For the following description it assumed that all non-positive edges have been removed from the path.

That leads to the following reduction to a longest path problem:

  • attach a sentinel edge of weight zero to the end of the path
  • generate a digraph whose nodes are the path-edges
  • connect pairs of nodes, that represent edges that are separated by 1 or 2 path edges, with a link that is directed from start to end of the path
  • associate the edge weights with the nodes.
  • construct the longest path by going from end-edge to start-edge and always let a node point to the target node with highest distance label and set the distance label of the current node to the sum of its successor distance plus its own weight.
  • report the cycle edges that correspond to the nodes of the longest path.

The complexity of that algorithm obviously is $O(n)$

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .