# Union grouping in bipartite graphs?

I'm trying to figure out a good (and fast) solution to the following problem:

I have two roles I'm working with, let's call them players and teams having many-to-many relationship (a player can be on multiple teams and a team can have multiple players). I'm working on creating a UI element on a form that allows a user to select multiple teams (checkboxes). As the user is selecting (or deselecting) teams, I'd like to display the teams grouped by the players.

So for examples:

1. If the selected teams have no common players, each team will have its own section.

2. If the user selects two teams and they have the same players, there would be one section containing the names of the two teams and all the players.

3. If TEAM_A has players [1, 2, 4, 5] and TEAM_B has players [1, 3, 5, 6]. There would be the following sections: SECTION_X = [TEAM_A, TEAM_B, 1, 5], SECTION_Y = [TEAM_A, 2, 3], SECTION _Z = [TEAM_B, 3, 5]

I hope that's clear. Essentially, I want to find the teams that players have in common and group by that. I was thinking maybe there is a way to do this by navigating a bipartite graph? Not exactly sure how though and I might be overthinking it. I was hoping to do this by creating some type of data structure on the server and using it on the client. I would love to hear your suggestions and I appreciate any help you can give!

• There can be an exponential number of ways to create these sections, do you have an objective function or criteria for such sections? – orezvani Oct 8 '14 at 16:46
• To me, it seems that the "longest common substring" is reducible to this problem and thus, it is NP-hard. Have you discovered the complexity class of this problem? – orezvani Oct 8 '14 at 16:46
• I haven't tried to reduce it. I don't have an objective function or criteria. The whole architecture around the problem is very flexible, I'm just trying to find a good way to solve it and then I can build around that. – Ian Oct 8 '14 at 17:01
• That's fair to look for a feasible solution, but how fast do you want the algorithm to be? Linear in terms of #teams and #players, square or cubic? – orezvani Oct 8 '14 at 17:09
• Best case is fast as possible. I'd definitely like it to be faster than the naive solution and I think ideally it would be linear with respect to the #teams. – Ian Oct 8 '14 at 17:24

I'll present an algorithm by example. Initialize a list of lists containing a list containing all of the players.

[[1, 2, 3, 4, 5, 6]]


For the first team, TEAM_A, replace each list by two lists, where the first list contains TEAM_A and the players on TEAM_A and the second list contains the players not on TEAM_A. Duplicate all of the existing team entries in both lists (none here).

[[TEAM_A, 1, 2, 4, 5], [3, 6]]


Discard all lists with no players (none here). For the second team, TEAM_B, replace each list by two lists, where the first list contains TEAM_B and the players on TEAM_B and the second list contains the players not on TEAM_B. Duplicate all of the existing team entries in both lists.

[[TEAM_B, TEAM_A, 1, 5], [TEAM_A, 2, 4], [TEAM_B, 3, 6], []]


Discard all lists with no players.

[[TEAM_B, TEAM_A, 1, 5], [TEAM_A, 2, 4], [TEAM_B, 3, 6]]


Well implemented, this should run in time proportional to the product of the number of teams and the number of players.

I'm assuming you want to maintain this data structure (essentially a Venn diagram) as edges are inserted and deleted. Maintain a hash table with the current regions, which is initialized as empty; each region contains a list of players using an appropriate data structure. For each player, maintain a pointer to its region.

When adding an edge connecting player $p$ to team $t$, locate the current region $R(p)$, and then:

1. Remove $p$ from $R(p)$. If $R(p)$ becomes empty then remove $R(p)$.
2. If $R(p) \cup \{t\}$ doesn't exist, add it. Then add $p$ to $R(p) \cup \{t\}$.
3. Assign $R(p) \cup \{t\}$ as the current region of $p$.

Deleting an edge is very similar and left to you.

There is also a simple offline solution. For each player $p$, calculate all teams $R(p)$ it belongs to. You get a list of pairs $(p,R(p))$, which you sort according to the second coordinate (either using a comparison-based sorting algorithm, or using radix sort). Now read off the regions. (When using radix sort, this is identical to David Eisenstat's suggestion.)