On the hardness of finding balanced independent sets in random bipartite graphs.

Will Perkins Yuzhou Wang

Published in: SODA (2024)

Keyphrases

bipartite graph
bipartite graph matching
maximum matching
link prediction
minimum weight
maximum cardinality
computational complexity
np complete
phase transition
graph clustering
machine learning
decision trees
np hard
social network analysis
edge weights
mutual reinforcement