Hello,

I have the following graph problem: Given is a Complete Bipartite Graph $$$G = (L, R)$$$ where $$$|L| = N \leq 100$$$ and $$$|R| = M \leq 10$$$ and an $$$N \times M$$$ array $$$C$$$ where the cost of the edge from the $$$l$$$th node of $$$L$$$ to the $$$r$$$th node of $$$R$$$ is given by $$$C[l][r] \leq 10^5$$$. I need to select a subset $$$S \subseteq E(G)$$$ of the edges such that:

• Every node $$$u \in L$$$ appears in exactly one edge of $$$S$$$
• Every node $$$v \in R$$$ appears in an odd number of edges of $$$S$$$

The cost of the selected set $$$S$$$ is defined as the sum of costs of individual edges of $$$S$$$. I have to find the set $$$S$$$ with the minimum cost.

I tried to reason about the optimal odd assignment being a small $$$(-1/0/1)$$$-deviation of the optimal assignment where nodes of $$$R$$$ can appear any number of times but I figured out this is not true.

One other approach I tried is to find an initial one to one matching $$$L'$$$ between $$$R$$$ and $$$L$$$ and then consider remaining nodes of $$$L$$$ as pairs and perform Min Cost Flow on the Tripartite Graph $$$G' = (L - L', M, R)$$$ where $$$M$$$ has a node for every pair of nodes in $$$L - L'$$$. But I couldn't prove that this will yield an optimal assignment for the original problem.

I think we should use the fact that $$$M$$$ is very small, that the bipartite graph is complete (anything can go to anything), and maybe that costs aren't arbitrarily large. Any help would be highly appreciated.

Thank you!

EDIT: Figured it out, turns out it was just Bitmask DP.