3
$\begingroup$

Consider a multi-edge bipartite graph $G = (L, R, E)$, with $|L| = |R| = n$, such that any $x \in L, y \in R$ have precisely two edges in $E$, $(x, y)_r, (x,y)_b$. We can imagine that we are assigning these edges a "color".

Given that each edge $e \in E$ has a weight assigned to it $w(e)$, is it possible to find the maximum weight matching in this graph, subject to constraints on the number of $r$ edges and $b$ edges?

I believe I have a proof that this problem is NP hard (reduction to 3-matching) when I can freely adjust the number of colors, but in the case of two colors, I haven't been able to find anything. I've been searching for the past couple of days for any existing literature on similar problems with no avail. I would appreciate any suggestions or directions in moving forward.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Hi ! What would be the idea of your reduction to 3-matching, with no color limit ? $\endgroup$
    – Hugo Manet
    Commented Mar 2, 2021 at 14:30
  • $\begingroup$ @HugoManet Perhaps Good question, I should clarify "multiple colors". When there are $n$ colors, I allow exactly $n$ edges between any two $x, y$. $\endgroup$
    – arealguru
    Commented Mar 3, 2021 at 0:06
  • 1
    $\begingroup$ @HugoManet That said, here's my informal argument idea: 1. Input: A tripartite hyper-graph $G = (X, Y, Z), E \subset X \times Y \times Z$. 2. Label each vertex in $Y$ with a distinct color. 3. Contract every edge $e \in E$; if there's a path from $x \rightarrow y \rightarrow z$, contract the edge to be an edge $x \rightarrow z$ and color this edge the same color as $y$. 4. Set weights in present edges to be $1$ and all others to be $0$. 5. Run the algorithm over contracted graph and the maximum weight matching is a 3 dimensional-matching (NP-Complete). $\endgroup$
    – arealguru
    Commented Mar 3, 2021 at 0:07
  • $\begingroup$ cstheory.stackexchange.com/q/48595/5038 $\endgroup$
    – D.W.
    Commented Mar 17, 2021 at 0:25

1 Answer 1

Reset to default
1
$\begingroup$

My guess is that, for a fixed number of colors, the problem is tractable. I'll work with 2 colors here but it should extend to any number (with a strong factor in the number of colors though).

The idea would be to solve simultaneously the problem for every constraint of $(r,b)$, using almost classical algorithms. But the augmenting paths you find in one instance don't necessarily impact that instance, but the neighboring instances instead, because the augmenting path might impact the $(r,b)$ balance.

There are some things left to investigate before applying that directly (classical pathfinding algorithm might not work straightforwardly because you need multiple solutions with different color balances), but this might just work.

With $k$ different colors, by counting the number of weak composition, you would have $n+k-1 \choose k-1$ such instances to consider, which is compatible with the NP-completeness reduction you found for $k = n$.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Which elementary algorithms would you suggest using? Also, I believe this would be polynomial only if the constraints on red and black edges is binding. If the constraints are $\leq r$ and $\leq b$, then does what you have in mind work still? $\endgroup$
    – arealguru
    Commented Mar 7, 2021 at 5:49
  • $\begingroup$ More or less all algorithms are the same : find augmenting paths, augment, and start over. This is the Ford-Fulkerson method (en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm), and various implementations try to do this as fast as possible, by computing several paths in parallel, or by finding paths efficiently, or by using heuristics to find augmenting path that go faster towards the optimal solution. I would suggest to try first the simple implementation of Ford-Fulkerson, to see if this approach works. If so, more efficient implementations should be possible. $\endgroup$
    – Hugo Manet
    Commented Mar 7, 2021 at 19:55
  • $\begingroup$ If you can compute it for every fixed constraint in polynomial time, then slack constraints are just about taking the minimum of all corresponding fixed constraints. $\endgroup$
    – Hugo Manet
    Commented Mar 7, 2021 at 19:57

You must log in to answer this question.

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