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

Will Perkins Yuzhou Wang

Published in: CoRR (2023)

Keyphrases

bipartite graph
bipartite graph matching
maximum matching
link prediction
minimum weight
maximum cardinality
worst case
lower bound
active learning
np hard
phase transition
keywords
computational complexity