# Algorithm to split bipartite graph into subgraphs

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.

• How do you quantify "the subgraphs should have as many customers as possible"? – Yuval Filmus Apr 3 '20 at 17:25
• 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. – Neil Brown Apr 3 '20 at 17:51
• 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? – Yuval Filmus Apr 3 '20 at 18:33

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.