# Tag Info

0

Let me start by answering a slightly different question: Given a weighted graph $G=(V,E)$ on $n=|V|$ vertices, we want to find a maximum-weight matching of cardinality at most $k$. Let $L$ be the largest edge weight in $G$, and define $L' = 2nL$. Transform the graph $G$ by adding $\ell =n-2k$ new vertices $v_1, \dots, v_\ell$, and all edges in \$\{v_1, \dots, ...

0

I found the answer myself at the end. Consider this graph and matching (full edge are matched and dashed are not) and suppose we start by exploring the red path from node 1 to 9: we cannot continue since entering node 7 would create a loop, but during this path we marked node 8 as visited from a non matched edge, and so we will not enter node 8 again ...

1

I think the issue will be that, if we allow each vertex to be considered twice (once per incoming edge type), then we need some way to remember that if we have already visited one "flavour" of a vertex on the path from the BFS root so far, we must avoid visiting its other flavour further along the same path (since such a path would no longer be ...

Top 50 recent answers are included