0
$\begingroup$

I'm looking for an algorithm to split a bipartite graph into subgraphs with a specific constraint. I'm not sure if any existing algorithms solve my problem or not.

I have an undirected bipartite graph where the nodes are customers ($C$) and services ($S$). I want to split this into several smaller subgraphs, limiting the amount of services in each subgraph to some maximum number $N$. Unfortunately, looking for disconnected subgraphs is not sufficient because the graph connectivity is too high, so I think I will need to duplicate services.

Formally, I want a set of subgraphs such that:

  • Each customer $c \in C$ appears in exactly one subgraph
  • All edges appear in exactly one subgraph (the one in which their customer appears)
  • Each service $s \in S$ can appear in any number of subgraphs (it's okay to duplicate services to help the split)
  • Each subgraph should have at most $N$ services (where $N$ is a given constant that is guaranteed to be larger than the highest number of services connected to any single customer)
  • The subgraphs should have as many customers as possible (without this restriction, it's trivially solvable by putting each customer in their own subgraph with a copy of their services). That can be a heuristic rather than formally proven.

Can anyone suggest an algorithm for doing this? The number of nodes is not huge (roughly 1000 customers, 100 services, with each customer connecting to 5 or less services) so brute force approaches or those with bad big-O scaling may be suitable.

Improve this question
$\endgroup$
3
  • $\begingroup$ How do you quantify "the subgraphs should have as many customers as possible"? $\endgroup$
    – Yuval Filmus
    Apr 3, 2020 at 17:25
  • $\begingroup$ The reason I added that is that the other constraints are satisfiable by having one customer per subgraph. So I figured I need something in the description (whether that's written as maximising customers per subgraph, or minimising number of subgraphs) to mean that I want to avoid this solution. I don't know the best way to express this, though. $\endgroup$
    – Neil Brown
    Apr 3, 2020 at 17:51
  • 3
    $\begingroup$ It's hard to shoot a moving target. Someone might come up with a solution, only for you to respond that you didn't have that measure in mind. Can you say anything at all on what a good solution would look like, and what are some examples of bad solutions? $\endgroup$
    – Yuval Filmus
    Apr 3, 2020 at 18:33

1 Answer 1

Reset to default
0
$\begingroup$

It smells like it might be NP-hard.

One plausible approach is to use a SAT solver or ILP solver. Suppose you decide you want to have at most $m$ subgraphs. Then you can have boolean variables $x_{i,k},y_{j,k}$ indicating that customer $i$ goes into subgraph $k$ and service $j$ goes into subgraph $k$. You can obtain a bunch of constraints (clauses) based on your requirements and then ask the SAT solver or ILP solver to find a feasible solution. The worst-case running time is exponential. This might or might not work well enough in your situation.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks; I had a try with Z3. I tried a model with booleans as you described and also using ints (each customer had a number indicating which single graph it was in). Both had similar runtime, and it's generally low enough for my purpose. Using maximisation to find the least subgraphs sent the runtime spiralling, so I instead used a hacky approach to try solving with 1 subgraph (which crucially also minimises number of bool vars needed) then 2 etc until a solution was found, and that was actually quicker. $\endgroup$
    – Neil Brown
    Apr 12, 2020 at 11:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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