2
$\begingroup$

Consider the following example problem. Given a graph with edge weights, find a matching that maximizes the number of matched vertices, and subject to this, maximizes the total weight. This problem can be reduced to simple maximum-weight matching as follows:

  • Construct a graph in which the weight of each edge $e$ is $(1, w_e)$, where $w_e$ is the weight of $e$ in the original graph.
  • Run any algorithm for finding a maximum-weight matching on the new graph, where the arithmetic operations (addition and subtraction) on the weights are done elementwise, and comparison (less-than or greater-than) is done in a lexicographic order. The returned matching maximizes a vector in which the first element is the number of matches and the second element is the total weight. The vector is maximum in lexicographic order, which is exactly what we wanted.

While there are other algorithms for this specific problem, the method is quite flexible and intuitive. For example, if we want to first maximize the total weight, and subject to this maximize the number of matches, then we should just change the vector weights to $(w_e, 1)$. If we want to maximize the number of matches in a particular subgroup of edges $F$, then the total number of matches, and then the total weight, we can change the vector weights on edges of $F$ to $(1, 1, w_e)$ and on other edges to $(0, 1, w_e)$.

My question is: can I assume that any algorithm for maximum-weight matching would work when the edge weights are vectors?

More generally: can I assume that any algorithm for weighted graphs would work with vector weights?

Are there algorithms that do not work with vector weights?

NOTE: In most textbooks, I see similar reductions done without vectors, e.g. by multiplying the first element by a sufficiently large number, and then adding the second element. I find the vector-weight explanation more simple and intuitive; this is why I ask if it is correct.

$\endgroup$

1 Answer 1

1
$\begingroup$

Let $M$ be a number which is larger than the weight of a maximum matching. For example, you can take $M$ to be $nW$, where $n$ is the number of vertices and $W$ is the maximal weight. Apply the transformation $w \mapsto M + w$, and run your favorite algorithm.

Similar tricks should work in other cases: apply the transformation $(v_1,\ldots,v_k) \mapsto M^{k-1} v_1 + \cdots + Mv_{k-1} + v_k$, where $M$ is large enough.

$\endgroup$

Your Answer

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

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