0
$\begingroup$

I'm trying to find a problem description that is roughly akin to a budgeted min-cost max-weight bipartite matching where the capacities are greater than 1. Imagine a max-flow problem on a graph that looks like this:

graph

Each node on the left is connected to a set of nodes on the right, but the nodes in that set on the right are only connected to that single node on the left. Add a super-source node to the left, a sink node to the right, and a super-sink node to the right of the sink node. Add a capacity into the super-sink representing the budget constraint. Each edge also gets a weight representing the value of that edge. We want to find the max flow through this graph with the minimum cost subject to the budget constraint, such that every edge having a flow is part of a matching set in the original bipartite graph (nodes 0-15 in the image). This represents each node on the left being forced to send flow through a single node in its "cluster" on the right. I feel like this is an NP-Hard problem, but I'm having trouble describing it.

Another way to think about it is that if we were solving the easier problem of just finding the max-flow, allowing any combination of center nodes (1-4, 7-10, and 12-15) to carry some of the flow, then this problem could be solved with a greedy algorithm that just waterfalls the budget into the nodes sorted by value. Forcing the flow to go through a single path per left node turns it into a different problem that I can't seem to find.

In summary, flows would be allowed to be on {0-2, 6-9, and 11-15}, but a solution where flows exist on {0-3, 0-4, 6-10, 11-13, 11-14} would not be valid.

Thanks!

$\endgroup$
7
  • $\begingroup$ I don't understand what you mean by "any "cluster" of nodes on the right only contains edges to a single node on the left" and "a left node doesn't link to more than one cluster on the right" - those two conditions don't sound equivalent. Can you edit your question to articulate what you mean more clearly? $\endgroup$
    – D.W.
    Mar 21, 2023 at 6:24
  • $\begingroup$ done. hope that helps. thanks. $\endgroup$ Mar 21, 2023 at 15:14
  • $\begingroup$ What does "every edge having a flow is part of a matching set" mean? Does it mean, at most one edge out of 0, at most one edge out of 6, at most one edge out of 11? $\endgroup$
    – D.W.
    Mar 22, 2023 at 2:20
  • $\begingroup$ yep. that's exactly what I mean. $\endgroup$ Mar 22, 2023 at 2:24
  • $\begingroup$ Can't you solve the problem for 0 separately, then solve the problem for 6 separately, then solve the problem for 11 separately? What am I missing? $\endgroup$
    – D.W.
    Mar 22, 2023 at 2:25

0

Your Answer

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