# A graph-based clustering problem

I have a graph in which each node is associated with a time stamp. I have around 15-20 nodes associated with each time stamp.

The edges are not weighted & there cannot be an edge between nodes which share a timestamp.

I'd like to find connected components of the graph but with the additional constraint that each discovered component can contain at most one node from each timestep.

I can easily find connected components using networkx in Python, but I'm not sure of the best way to enforce the constraint. Often the connected components contain multiple nodes with the same timestamp.

It feels like the best way to proceed is to treat each connected component as a subgraph and try to find an optimal way of removing edges to enforce the constraint. I want to remove the fewest possible edges such that the constraint is satisfied.

I'm not quite sure how to do that. Any help would be much appreciated.

EDIT:

Here is an example of the subgraph for the largest connected component

It's the edges in the middle that are causing the problem. I essentially want to find the edges to remove which optimally break off the branches, which each contain at most one node from each timestep.

EDIT 2:

I tried a greedy approach whereby I score each edge according to the total number of constraint violations if that edge is removed. I then remove the edge that leads to the greatest improvement. I do this until there are no constraint violations left. It doesn't even get close to the solution I'm looking for. I end up removing almost all of the edges.

• With the extra constrain, the connected components are not unique. I assume you want to get the minimum number of connected components (i.e. dont split the graph to too many small components)? Or what metrics, if any, you want to optimize? Commented Feb 4, 2020 at 15:44
• Yes that's right. I want to remove the smallest number of edges such that the constraint is met, or alternatively obtain the smallest possible number of new components such that the constraint is met. If there are still multiple equally 'good' solutions, I'm happy to pick one at random or come up with some other heuristic to choose between the options.
– Will
Commented Feb 4, 2020 at 15:50